BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Sariel Har-Peled

Sariel Har-Peled contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryData Structures and AlgorithmsDatabasesMachine Learningmath.DG

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
22works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

22 published item(s)

preprint2026arXiv

An Output Sensitive Algorithm for Discrete Convex Hulls

$\def\DD{\bf δ}\def\CH{\mathop{\mathrm{ConvexHull}}}\newcommand{\LL}{\cal {L}} \newcommand{\ZZ}{\mathbb{Z}} $ Given a convex body $C$ in the plane, its discrete hull is $C^0 = \CH( C \cap \LL )$, where $\LL = \ZZ \times \ZZ$ is the integer lattice. We present an $O( |C^0| \log \DD(C) )$-time algorithm for calculating the discrete hull of $C$, where $|C^0|$ denotes the number of vertices of $C^0$, and $\DD(C)$ is the diameter of $C$. Actually, using known combinatorial bounds, the running time of the algorithm is $O(\DD(C)^{2/3} \log{\DD(C)})$. In particular, this bound applies when $C$ is a disk.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

How to Get Close to the Median Shape

$\renewcommand{\Re}{\mathbb{R}}\newcommand{\eps}{\varepsilon}\newcommand{\poly}{\mathrm{poly}} $In this paper, we study the problem of $L_1$-fitting a shape to a set of $n$ points in $\Re^d$ (where $d$ is a fixed constant), where the target is to minimize the sum of distances of the points to the shape, or the sum of squared distances. We present a general technique for computing a $(1 + \eps ) $-approximation for such a problem, with running time $O(n + \poly( \log n, 1/\eps))$, where $\poly(\log n, 1/\eps)$ is a polynomial of constant degree of $\log n$ and $1/\eps$ (the power of the polynomial is a function of $d$). The new algorithm runs in linear time for a fixed $\eps>0$, and is the first subquadratic algorithm for this problem. Applications of the algorithm include best fitting either a circle, a sphere, or a cylinder to a set of points when minimizing the sum of distances (or squared distances) to the respective shape.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

In the Search for Good Neck Cuts

We study the problem of finding neck-like features on a surface. Applications for such cuts include robotics, mesh segmentation, and algorithmic applications. We provide a new definition for a surface bottleneck -- informally, it is the shortest cycle relative to the size of the areas it separates. Inspired by the isoperimetric inequality, we formally define such optimal cuts, study their properties, and present several algorithms inspired by these ideas that work surprisingly well in practice. For examples of our algorithms, see https://neckcut.space.

0 citations0 reviewsNo code linkedOpen access
preprint2025arXiv

The Complexity of One or Many Faces in the Overlay of Many Arrangements

We present an extension of the Combination Lemma of [GSS89] that expresses the complexity of one or several faces in the overlay of many arrangements, as a function of the number of arrangements, the number of faces, and the complexities of these faces in the separate arrangements. Several applications of the new Combination Lemma are presented: We first show that the complexity of a single face in an arrangement of $k$ simple polygons with a total of $n$ sides is $Θ(n α(k) )$, where $α(\cdot)$ is the inverse of Ackermann's function. We also give a new and simpler proof of the bound $O \left( \sqrt{m} λ_{s+2}( n ) \right)$ on the total number of edges of $m$ faces in an arrangement of $n$ Jordan arcs, each pair of which intersect in at most $s$ points, where $λ_{s}(n)$ is the maximum length of a Davenport-Schinzel sequence of order $s$ with $n$ symbols. We extend this result, showing that the total number of edges of $m$ faces in a sparse arrangement of $n$ Jordan arcs is $O \left( (n + \sqrt{m}\sqrt{w}) \frac{λ_{s+2}(n)}{n} \right)$, where $w$ is the total complexity of the arrangement. Several other applications and variants of the Combination Lemma are also presented.

0 citations0 reviewsNo code linkedOpen access
preprint2025arXiv

The Fréchet Distance Unleashed: Approximating a Dog with a Frog

We show that a variant of the continuous Frechet distance between polygonal curves can be computed using essentially the same algorithm used to solve the discrete version. The new variant is not necessarily monotone, but this shortcoming can be easily handled via refinement. Combined with a Dijkstra/Prim type algorithm, this leads to a realization of the Frechet distance (i.e., a morphing) that is locally optimal (aka locally correct), that is both easy to compute, and in practice, takes near linear time on many inputs. The new morphing has the property that the leash is always as short as possible. These matchings/morphings are more natural and are better than the ones computed by standard algorithms -- in particular, they handle noise more graciously. This approach should make the Frechet distance more useful for real-world applications. We implemented the new algorithm and various strategies to obtain reasonably fast practical performance. We performed extensive experiments on our new algorithm, and released publicly available (and easily installable and usable) Julia and Python packages. Our algorithms can be used to compute the almost-exact Frechet distance between polygonal curves. Implementations and numerous examples are available here: https://frechet.xyz. We emphasize, however, that the existing state-of-the-art algorithm/implementation in C++ is faster, by several orders of magnitude, than our current algorithm/implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

On the Width of the Regular $n$-Simplex

Consider the regular $n$-simplex $Δ_n$ - it is formed by the convex-hull of $n+1$ points in Euclidean space, with each pair of points being in distance exactly one from each other. We prove an exact bound on the width of $Δ_n$ which is $\approx \sqrt{2/n}$. Specifically, $ \mathrm{width}(Δ_n) = \sqrt{\frac{2}{n + 1}}$ if $n$ is odd, and $ \mathrm{width}(Δ_n) = \sqrt{\frac{2(n+1)}{n(n+2)}} $ if $n$ is even. While this bound is well known [GK92, Ale77], we provide a self-contained elementary proof that might (or might not) be of interest.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Note on Stabbing Convex Bodies with Points, Lines, and Flats

$\newcommand{\eps}{\varepsilon}\newcommand{\tldO}{\widetilde{O}}$Consider the problem of constructing weak $\eps$-nets where the stabbing elements are lines or $k$-flats instead of points. We study this problem in the simplest setting where it is still interesting -- namely, the uniform measure of volume over the hypercube $[0,1]^d\bigr.$. Specifically, a $(k,\eps)$-net is a set of $k$-flats, such that any convex body in $[0,1]^d$ of volume larger than $\eps$ is stabbed by one of these $k$-flats. We show that for $k \geq 1$, one can construct $(k,\eps)$-nets of size $O(1/\eps^{1-k/d})$. We also prove that any such net must have size at least $Ω(1/\eps^{1-k/d})$. As a concrete example, in three dimensions all $\eps$-heavy bodies in $[0,1]^3$ can be stabbed by $Θ(1/\eps^{2/3})$ lines. Note, that these bounds are \emph{sublinear} in $1/\eps$, and are thus somewhat surprising. The new construction also works for points providing a weak $\eps$-net of size $O(\tfrac{1}{\eps}\log^{d-1} \tfrac{1}{\eps} )$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

We present a $(1- \varepsilon)$-approximation algorithms for maximum cardinality matchings in disk intersection graphs -- all with near linear running time. We also present estimation algorithm that returns $(1\pm \varepsilon)$-approximation to the size of such matchings -- this algorithms run in linear time for unit disks, and $O(n \log n)$ for general disks (as long as the density is relatively small).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Halving by a Thousand Cuts or Punctures

$\newcommand{\Arr}{\mathcal{A}} \newcommand{\numS}{k} \newcommand{\ArrX}[1]{\Arr(#1)} \newcommand{\eps}{\varepsilon} \newcommand{\opt}{\mathsf{o}}$ For point sets $P_1, \ldots, P_\numS$, a set of lines $L$ is halving if any face of the arrangement $\ArrX{L}$ contains at most $|P_i|/2$ points of $P_i$, for all $i$. We study the problem of computing a halving set of lines of minimal size. Surprisingly, we show a polynomial time algorithm that outputs a halving set of size $O(\opt^{3/2})$, where $\opt$ is the size of the optimal solution. Our solution relies on solving a new variant of the weak $\eps$-net problem for corridors, which we believe to be of independent interest. We also study other variants of this problem, including an alternative setting, where one needs to introduce a set of guards (i.e., points), such that no convex set avoiding the guards contains more than half the points of each point set.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Local Spanners Revisited

$\newcommand{\Emph}[1]{\it{#1}} \newcommand{\FF}{\mathcal{F}}\newcommand{\region}{\mathsf{r}}\newcommand{\restrictY}[2]{#1 \cap {#2}}$For a set of points $P \subseteq \mathbb{R}^2$, and a family of regions $\FF$, a $\Emph{local~t-spanner}$ of $P$, is a sparse graph $G$ over $P$, such that, for any region $\region \in \FF$, the subgraph restricted to $\region$, denoted by $\restrictY{G}{\region} = G_{P \cap \region}$, is a $t$-spanner for all the points of $\region \cap P$. We present algorithms for the construction of local spanners with respect to several families of regions, such as homothets of a convex region. Unfortunately, the number of edges in the resulting graph depends logarithmically on the spread of the input point set. We prove that this dependency can not be removed, thus settling an open problem raised by Abam and Borouny. We also show improved constructions (with no dependency on the spread) of local spanners for fat triangles, and regular $k$-gons. In particular, this improves over the known construction for axis parallel squares. We also study a somewhat weaker notion of local spanner where one allows to shrink the region a "bit". Any spanner is a weak local spanner if the shrinking is proportional to the diameter. Surprisingly, we show a near linear size construction of a weak spanner for axis-parallel rectangles, where the shrinkage is $\Emph{multiplicative}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sometimes Reliable Spanners of Almost Linear Size

Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, a reliable spanner may have some additional vertices for which the spanner property no longer holds, but this collateral damage is bounded by a fraction of the size of the attack. It is known that $Ω(n\log n)$ edges are needed to achieve this strong property, where $n$ is the number of vertices in the network, even in one dimension. Constructions of reliable geometric $(1+\varepsilon)$-spanners, for $n$ points in $\Re^d$, are known, where the resulting graph has $O( n \log n \log \log^{6}n )$ edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical -- replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip-list like construction. This results in a $1$-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in $\Re^d$ with $O( n \log \log^{2} n \log \log \log n )$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sparsifying Disk Intersection Graphs for Reliable Connectivity

The intersection graph induced by a set $\Disks$ of $n$ disks can be dense. It is thus natural to try and sparsify it, while preserving connectivity. Unfortunately, sparse graphs can always be made disconnected by removing a small number of vertices. In this work, we present a sparsification algorithm that maintains connectivity between two disks in the computed graph, if the original graph remains ``well-connected'' even after removing an arbitrary ``attack'' set $\BSet \subseteq \Disks$ from both graphs. Thus, the new sparse graph has similar reliability to the original disk graph, and can withstand catastrophic failure of nodes while still providing a connectivity guarantee for the remaining graph. The new graphs has near linear complexity, and can be constructed in near linear time. The algorithm extends to any collection of shapes in the plane, such that their union complexity is near linear.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?

Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points $S$ and a radius parameter $r>0$, the $r$-near neighbor ($r$-NN) problem asks for a data structure that, given any query point $q$, returns a point $p$ within distance at most $r$ from $q$. In this paper, we study the $r$-NN problem in the light of individual fairness and providing equal opportunities: all points that are within distance $r$ from the query should have the same probability to be returned. In the low-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS 2014). Locality sensitive hashing (LSH), the theoretically strongest approach to similarity search in high dimensions, does not provide such a fairness guarantee. In this work, we show that LSH based algorithms can be made fair, without a significant loss in efficiency. We propose several efficient data structures for the exact and approximate variants of the fair NN problem. Our approach works more generally for sampling uniformly from a sub-collection of sets of a given collection and can be used in a few other applications. We also develop a data structure for fair similarity search under inner product that requires nearly-linear space and exploits locality sensitive filters. The paper concludes with an experimental evaluation that highlights the inherent unfairness of NN data structures and shows the performance of our algorithms on real-world datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Spanner for the Day After

We show how to construct $(1+\varepsilon)$-spanner over a set $P$ of $n$ points in $\mathbb{R}^d$ that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $\vartheta,\varepsilon \in (0,1)$, the computed spanner $G$ has $ O\bigl(\varepsilon^{-c} \vartheta^{-6} n \log n (\log\log n)^6 \bigr) $ edges, where $c= O(d)$. Furthermore, for any $k$, and any deleted set $B \subseteq P$ of $k$ points, the residual graph $G \setminus B$ is $(1+\varepsilon)$-spanner for all the points of $P$ except for $(1+\vartheta)k$ of them. No previous constructions, beyond the trivial clique with $O(n^2)$ edges, were known such that only a tiny additional fraction (i.e., $\vartheta$) lose their distance preserving connectivity. Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black box fashion.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Edge Estimation with Independent Set Oracles

We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an $n$-vertex graph, using (i) $\mathrm{polylog}(n)$ bipartite independent set queries, or (ii) ${n}^{2/3} \cdot\mathrm{polylog}(n)$ independent set queries.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Locality-Sensitive Orderings and their Applications

For any constant $d$ and parameter $\varepsilon > 0$, we show the existence of (roughly) $1/\varepsilon^d$ orderings on the unit cube $[0,1)^d$, such that any two points $p,q\in [0,1)^d$ that are close together under the Euclidean metric are "close together" in one of these linear orderings in the following sense: the only points that could lie between $p$ and $q$ in the ordering are points with Euclidean distance at most $\varepsilon\| p - q \|$ from $p$ or $q$. These orderings are extensions of the $\mathcal{Z}$-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Some Geometric Applications of Anti-Chains

We present an algorithmic framework for computing anti-chains of maximum size in geometric posets. Specifically, posets in which the entities are geometric objects, where comparability of two entities is implicitly defined but can be efficiently tested. Computing the largest anti-chain in a poset can be done in polynomial time via maximum-matching in a bipartite graph, and this leads to several efficient algorithms for the following problems, each running in (roughly) $O(n^{3/2})$ time: (A) Computing the largest Pareto-optimal subset of a set of $n$ points in $\mathbb{R}^d$. (B) Given a set of disks in the plane, computing the largest subset of disks such that no disk contains another. This is quite surprising, as the independent version of this problem is computationally hard. (C) Given a set of axis-aligned rectangles, computing the largest subset of non-crossing rectangles.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Submodular Clustering in Low Dimensions

We study a clustering problem where the goal is to maximize the coverage of the input points by $k$ chosen centers. Specifically, given a set of $n$ points $P \subseteq \mathbb{R}^d$, the goal is to pick $k$ centers $C \subseteq \mathbb{R}^d$ that maximize the service $ \sum_{p \in P}\mathsfφ\bigl( \mathsf{d}(p,C) \bigr) $ to the points $P$, where $\mathsf{d}(p,C)$ is the distance of $p$ to its nearest center in $C$, and $\mathsfφ$ is a non-increasing service function $\mathsfφ : \mathbb{R}^+ \to \mathbb{R}^+$. This includes problems of placing $k$ base stations as to maximize the total bandwidth to the clients -- indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place $k$ base stations so that the total bandwidth is maximized. We provide an $n^{\varepsilon^{-O(d)}}$ time algorithm for this problem that achieves a $(1-\varepsilon)$-approximation. Notably, the runtime does not depend on the parameter $k$ and it works for an arbitrary non-increasing service function $\mathsfφ : \mathbb{R}^+ \to \mathbb{R}^+$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Maximum-Level Vertex in an Arrangement of Lines

Let $L$ be a set of $n$ lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement $A(L)$ of maximum level, where the level of a vertex $v$ is the number of lines of $L$ that pass strictly below $v$. The problem, posed in Exercise~8.13 in de Berg etal [BCKO08], appears to be much harder than it seems, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of $L$ are distinct, and distinguish between two cases, depending on whether or not the upper envelope of $L$ contains a bounded edge. In the former case, we show that the number of lines of $L$ that pass above any maximum level vertex $v_0$ is only $O(\log n)$. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal $O(n\log n)$ time. We then consider the case where the lines of $L$ are not necessarily distinct. This setup is more challenging, and the best we have is an algorithm that computes all the maximum-level vertices in time $O(n^{4/3}\log^{3}n)$. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weighted $k$-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is $O(n^{4/3})$, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Grid peeling and the affine curve-shortening flow

In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. The first one (which we call "grid peeling") is the convex-layer decomposition of subsets $G\subset \mathbb Z^2$ of the integer grid, previously studied for the particular case $G=\{1,\ldots,m\}^2$ by Har-Peled and Lidický (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (1993) and Sapiro and Tannenbaum (1993). We present empirical evidence that, in a certain well-defined sense, grid peeling behaves at the limit like ACSF on convex curves. We offer some theoretical arguments in favor of this conjecture. We also pay closer attention to the simple case where $G=\mathbb N^2$ is a quarter-infinite grid. This case corresponds to ACSF starting with an infinite L-shaped curve, which when transformed using the ACSF becomes a hyperbola for all times $t>0$. We prove that, in the grid peeling of $\mathbb N^2$, (1) the number of grid points removed up to iteration $n$ is $Θ(n^{3/2}\log n)$; and (2) the boundary at iteration $n$ is sandwiched between two hyperbolas that are separated from each other by a constant factor.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximate Greedy Clustering and Distance Selection for Graph Metrics

$\newcommand{\eps}{\varepsilon}$ In this paper, we consider two important problems defined on finite metric spaces, and provide efficient new algorithms and approximation schemes for these problems on inputs given as graph shortest path metrics or high-dimensional Euclidean metrics. The first of these problems is the greedy permutation (or farthest-first traversal) of a finite metric space: a permutation of the points of the space in which each point is as far as possible from all previous points. We describe randomized algorithms to find $(1+\eps)$-approximate greedy permutations of any graph with $n$ vertices and $m$ edges in expected time $O(\eps^{-1}(m+n)\log n\log(n/\eps))$, and to find $(1+\eps)$-approximate greedy permutations of points in high-dimensional Euclidean spaces in expected time $O(\eps^{-2} n^{1+1/(1+\eps)^2 + o(1)})$. Additionally we describe a deterministic algorithm to find exact greedy permutations of any graph with $n$ vertices and treewidth $O(1)$ in worst-case time $O(n^{3/2}\log^{O(1)} n)$. The second of the two problems we consider is distance selection: given $k \in [ \binom{n}{2} ]$, we are interested in computing the $k$th smallest distance in the given metric space. We show that for planar graph metrics one can approximate this distance, up to a constant factor, in near linear time.

0 citations0 reviewsNo code linkedOpen access