93 citations · 292 across the 46 of their papers we have counts for
5 papers · 1 filter
Optimal randomized incremental construction for guaranteed logarithmic planar point location
Michael Hemmer, Michal Kleinbort, Dan Halperin
Given a planar map of segments in which we wish to efficiently locate points, we present the first randomized incremental construction of the well-known trapezoidal-map search-…
Efficient high-quality motion planning by fast all-pairs r-nearest-neighbors
Michal Kleinbort, Oren Salzman, Dan Halperin
Sampling-based motion-planning algorithms typically rely on nearest-neighbor (NN) queries when constructing a roadmap. Recent results suggest that in various settings NN queries ma…
On the hardness of unlabeled multi-robot motion planning
Kiril Solovey, Dan Halperin
In unlabeled multi-robot motion planning several interchangeable robots operate in a common workspace. The goal is to move the robots to a set of target positions such that each po…
The Offset Filtration of Convex Objects
Dan Halperin, Michael Kerber, Doron Shaharabani
We consider offsets of a union of convex objects. We aim for a filtration, a sequence of nested cell complexes, that captures the topological evolution of the offsets for increasin…
Asymptotically-Optimal Motion Planning using Lower Bounds on Cost
Oren Salzman, Dan Halperin
Many path-finding algorithms on graphs such as A* are sped up by using a heuristic function that gives lower bounds on the cost to reach the goal. Aiming to apply similar technique…