6 papers
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…
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…
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…
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
Pankaj K. Agarwal, Boris Aronov, Esther Ezra +2
Let be a set of flat (planar) semi-algebraic regions in of constant complexity (e.g., triangles, disks), which we call plates. We wish to preproces…
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…