158 citations · 543 across the 80 of their papers we have counts for
105 papers
Point and Line Nearest-Neighbor Searching in 3-Space
Pankaj K. Agarwal, Esther Ezra, Micha Sharir
This paper presents data structures for nearest-neighbor (NN) searching problems involving points, lines, segments, and triangles in 3-space, achieving significantly better perform…
Efficient Algorithms for the Bottleneck Path Problem in Geometric Graphs
Matthew J. Katz, Rachel Saban, Micha Sharir
We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna…
Nearly-Tight Bounds for Vertical Decomposition in Three and Four Dimensions
Pankaj K. Agarwal, Esther Ezra, Micha Sharir
Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in into constant-complexity subcells. In…
Dynamic Nearest-Neighbor Searching Under General Metrics in and Its Applications
Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir
Let be a compact, centrally-symmetric, strictly-convex region in , which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding me…
Implicit representations via the polynomial method
Jean Cardinal, Micha Sharir
Semialgebraic graphs are graphs whose vertices are points in , and adjacency between two vertices is determined by the truth value of a semialgebraic predicate of con…
Covering points by hyperplanes and related problems
Zuzana Patáková, Micha Sharir
For a set of points in , for any , a hyperplane is called -rich with respect to if it contains at least points of . Answering and gen…