Lower bounds for intersection searching and fractional cascading in higher dimension

摘要

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.