272 citations · 611 across the 76 of their papers we have counts for
83 papers · 1 filter
The Quick Dog Jumps the Log
Lotte Blank, Anne Driemel, Sariel Har-Peled +1
We give linear-time, and thus optimal, -approximation algorithms for numerous variants of the Frechet distance between -packed curves (where ), remo…
How to Get Close to the Median Shape
Sariel Har-Peled
In this paper, we study the problem of -fitting a shape to a set of points…
An Output Sensitive Algorithm for Discrete Convex Hulls
Sariel Har-Peled
Given a convex body in the plane, its discrete hull is $C^0 = \CH(…
The Complexity of One or Many Faces in the Overlay of Many Arrangements
Sariel Har-Peled
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 o…
Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard
Gill Barequet, Sariel Har-Peled
The 3SUM problem represents a class of problems conjectured to require time to solve, where is the size of the input. Given two polygons and in the plane, we s…
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
Gill Barequet, Sariel Har-Peled
We present an efficient -time algorithm for computing a )-approximation of the minimum-volume bounding…
New Constructions of SSPDs and their Applications
Mohammad A. Abam, Sariel Har-Peled
We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of points in . In the new constructio…
A Practical Approach for Computing the Diameter of a Point Set
Sariel Har-Peled
We present an approximation algorithm for computing the diameter of a point-set in . The new algorithm is sensitive to the ``hardness'' of computing the diameter of the give…
On the Width of the Regular -Simplex
Sariel Har-Peled, Eliot W. Robson
Consider the regular -simplex - it is formed by the convex-hull of points in Euclidean space, with each pair of points being in distance exactly one from each other.…
Computing Optimal Kernels in Two Dimensions
Pankaj K. Agarwal, Sariel Har-Peled
Let be a set of points in . For a parameter , a subset is an \emph{-kernel} of if the projection of the convex…
On Clusters that are Separated but Large
Sariel Har-Peled, Joseph Rogge
Given a set of points in , consider the problem of computing subsets of that form clusters that are well-separated from each…
How Packed Is It, Really?
Sariel Har-Peled, Timothy Zhou
The congestion of a curve is a measure of how much it zigzags around locally. More precisely, a curve is -packed if the length of the curve lying inside any ball is at most…
On Undecided LP, Clustering and Active Learning
Stav Ashur, Sariel Har-Peled
We study colored coverage and clustering problems. Here, we are given a colored point set where the points are covered by (unknown) clusters, which are monochromatic (i.e., all…
Shortest Secure Path in a Voronoi Diagram
Sariel Har-Peled, Rajgopal Varadharajan
We investigate the problem of computing the shortest secure path in a Voronoi diagram. Here, a path is secure if it is a sequence of touching Voronoi cells, where each Voronoi cell…
Reliable Spanners for Metric Spaces
Sariel Har-Peled, Manor Mendel, Dániel Oláh
A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining grap…
Improved Approximation Algorithms for Tverberg Partitions
Sariel Har-Peled, Timothy Zhou
Tverberg's theorem states that a set of points in can be partitioned into $\flo…
Submodular Clustering in Low Dimensions
Arturs Backurs, Sariel Har-Peled
We study a clustering problem where the goal is to maximize the coverage of the input points by chosen centers. Specifically, given a set of points $P \subseteq \mathbb{R}^…
The Maximum-Level Vertex in an Arrangement of Lines
Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn +2
Let be a set of lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement of maximum…
Covering Polygons by Min-Area Convex Polygons
Elias Dahlhaus, Sariel Har-Peled, Alan L. Hu
Given a set of disjoint simple polygons , of total complexity , consider a convexification process that repeatedly replaces a polygon by its convex hull, and a…
Proof of Dudley's Convex Approximation
Sariel Har-Peled, Mitchell Jones
We provide a self contained proof of a result of Dudley [Dud64]} which shows that a bounded convex-body in can be -approximated, by the intersection of $O_d\bi…
Optimal Algorithms for Geometric Centers and Depth
Timothy M. Chan, Sariel Har-Peled, Mitchell Jones
We develop a general randomized technique for solving "implic it" linear programming problems, where the collection of constraints are defined impl…
Sometimes Reliable Spanners of Almost Linear Size
Kevin Buchin, Sariel Har-Peled, Daniel Olah
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…
Some Geometric Applications of Anti-Chains
Sariel Har-Peled, Mitchell Jones
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 comparabi…
Smallest k-Enclosing Rectangle Revisited
Timothy M. Chan, Sariel Har-Peled
Given a set of points in the plane, and a parameter , we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing points. We pr…