Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 269-284 |
Number of pages | 16 |
Journal | Journal of Computer and System Sciences |
Volume | 68 |
Issue number | 2 |
DOIs | |
State | Published - Mar 2004 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science
- Applied Mathematics
- Computer Networks and Communications
- Computational Theory and Mathematics