2001/07/06 by Bernard Chazelle, Ding Liu · 3 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics #Robotic Path Planning Algorithms
paper · doi:10.1145/380752.380818
openalex publication_date 2001/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Given an n-edge convex subdivision of the plane, is it possible to report its k intersections with a query line segment in O(k+~polylog(n)) time, using subquadratic storage? If the query is a plane and the input is a polytope with n vertices, can one achieve O(k+~polylog(n)) time with subcubic storage? Does any convex polytope have a boundary dominant Dobkin-Kirkpatrick hierarchy? Can fractional cascading be generalized to planar maps instead of linear lists? We prove that the answer to all of these questions is no, and we derive near-optimal solutions to these classical problems.