Lower bounds for intersection searching and fractional cascading in higher dimension

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

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 languageEnglish (US)
Pages (from-to)269-284
Number of pages16
JournalJournal of Computer and System Sciences
Volume68
Issue number2
DOIs
StatePublished - Mar 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Lower bounds for intersection searching and fractional cascading in higher dimension'. Together they form a unique fingerprint.

Cite this