Lower bounds for intersection searching and fractional cascading in higher dimension

B. Chazelle, D. Liu

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations


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 subcubie 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.

Original languageEnglish (US)
Pages (from-to)322-329
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2001
Event33rd Annual ACM Symposium on Theory of Computing - Creta, Greece
Duration: Jul 6 2001Jul 8 2001

All Science Journal Classification (ASJC) codes

  • Software

Cite this