272 citations · 611 across the 76 of their papers we have counts for
8 papers · 1 filter
On the Expected Complexity of Voronoi Diagrams on Terrains
Anne Driemel, Sariel Har-Peled, Benjamin Raichel
We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov etal [ABT08] prove that, if one makes certain…
Minimum Convex Partitions and Maximum Empty Polytopes
Adrian Dumitrescu, Sariel Har-Peled, Csaba D. Tóth
Let be a set of points in . A Steiner convex partition is a tiling of with empty convex bodies. For every integer , we show that admits…
On the Expected Complexity of Random Convex Hulls
Sariel Har-Peled
In this paper we present several results on the expected complexity of a convex hull of points chosen uniformly and independently from a convex shape. (i) We show that the expe…
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space
Sariel Har-Peled, Nirman Kumar
For a set of points in , and parameters and $\eps$, we present a data structure that answers $(1+\eps,k)$-\ANN queries in logarithmic time. Surprisingly, the space u…
Geometric Packing under Non-uniform Constraints
Alina Ene, Sariel Har-Peled, Benjamin Raichel
We study the problem of discrete geometric packing. Here, given weighted regions (say in the plane) and points (with capacities), one has to pick a maximum weight subset of the reg…
Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts
Anne Driemel, Sariel Har-Peled
The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut betwe…