33 citations · 45 across the 30 of their papers we have counts for
9 papers · 1 filter
The Road to the Closest Point is Paved by Good Neighbors
Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson
Given a set of points in , and a parameter , we present a new construction of a directed graph , of size $O…
Bifurcation: How to Explore a Tree
Sariel Har-Peled
Avraham et al. [AFK+15] presented an alternative approach to parametric search, called \emph{bifurcation}, that performs faster under certain circumstances. Intuitively, when the u…
Well-Separated Pairs Decomposition Revisited
Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson
We revisit the notion of WSPD (i.e., well-separated pairs-decomposition), presenting a new construction of WSPD for any finite metric space, and show that it is asymptotically inst…
An Easy Proof of a Weak Version of Chernoff inequality
Sariel Har-Peled
We prove an easy but very weak version of Chernoff inequality. Namely, that the probability that in throws of a fair coin, one gets at most heads is .
Edge Nearest Neighbor in Sampling-Based Motion Planning
Stav Ashur, Nancy M. Amato, Sariel Har-Peled
Neighborhood finders and nearest neighbor queries are fundamental parts of sampling based motion planning algorithms. Using different distance metrics or otherwise changing the def…
Faster Motion Planning via Restarts
Nancy Amato, Stav Ashur, Sariel Har-Peled%
Randomized methods such as PRM and RRT are widely used in motion planning. However, in some cases, their running-time suffers from inherent instability, leading to ``catastrophic''…
Improving the average dilation of a metric graph by adding edges
Sariel Har-Peled, Eliot W. Robson
For a graph spanning a metric space, the dilation of a pair of points is the ratio of their distance in the shortest path graph metric to their distance in the metric space. Gi…
Orthogonal Emptiness Queries for Random Points
Jonathan E. Dullerud, Sariel Har-Peled
We present a data-structure for orthogonal range searching for random points in the plane. The new data-structure uses (in expectation) sp…
Quickly Avoiding a Random Catastrophe
Stav Ashur, Sariel Har-Peled
We study the problem of constructing simulations of a given randomized search algorithm \texttt{alg} with expected running time , where $\mathcal{…