11 papers
The Quick Dog Jumps the Log
Lotte Blank, Anne Driemel, Anne Drieme +2
We give linear-time, and thus optimal, -approximation algorithms for numerous variants of the Frechet distance between -packed curves (where ), remo…
Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
Sariel Har-Peled, Banjamin Raichel
We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTASs) to several well-known problems in Computational Geometry,…
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…