Lower bounds for intersection searching and fractional cascading in higher dimension

Bernard Chazelle; Ding Liu

doi:10.1016/j.jcss.2003.07.003

Lower bounds for intersection searching and fractional cascading in higher dimension

Bernard Chazelle, Ding Liu

Research output: Contribution to journal › Article › peer-review

15 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 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	https://doi.org/10.1016/j.jcss.2003.07.003
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

Access to Document

10.1016/j.jcss.2003.07.003

Cite this

@article{a55e2b4599cf4e8591a3723f53ed6e8e,

title = "Lower bounds for intersection searching and fractional cascading in higher dimension",

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.",

author = "Bernard Chazelle and Ding Liu",

year = "2004",

month = mar,

doi = "10.1016/j.jcss.2003.07.003",

language = "English (US)",

volume = "68",

pages = "269--284",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Lower bounds for intersection searching and fractional cascading in higher dimension

AU - Chazelle, Bernard

AU - Liu, Ding

PY - 2004/3

Y1 - 2004/3

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

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

UR - https://www.scopus.com/pages/publications/1842510630

UR - https://www.scopus.com/inward/citedby.url?scp=1842510630&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2003.07.003

DO - 10.1016/j.jcss.2003.07.003

M3 - Article

AN - SCOPUS:1842510630

SN - 0022-0000

VL - 68

SP - 269

EP - 284

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Lower bounds for intersection searching and fractional cascading in higher dimension

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this