Lower bounds for intersection searching and fractional cascading in higher dimension

B. Chazelle; D. Liu

doi:10.1145/380752.380818

Lower bounds for intersection searching and fractional cascading in higher dimension

B. Chazelle, D. Liu

Research output: Contribution to journal › Conference article › peer-review

5 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 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 language	English (US)
Pages (from-to)	322-329
Number of pages	8
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/380752.380818
State	Published - 2001
Event	33rd Annual ACM Symposium on Theory of Computing - Creta, Greece Duration: Jul 6 2001 → Jul 8 2001

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/380752.380818

Cite this

@article{d999be9ae8724244b3e57e269fa2ce9c,

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

author = "B. Chazelle and D. Liu",

year = "2001",

doi = "10.1145/380752.380818",

language = "English (US)",

pages = "322--329",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "33rd Annual ACM Symposium on Theory of Computing ; Conference date: 06-07-2001 Through 08-07-2001",

}

TY - JOUR

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

AU - Chazelle, B.

AU - Liu, D.

PY - 2001

Y1 - 2001

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

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

UR - http://www.scopus.com/inward/record.url?scp=0034826414&partnerID=8YFLogxK

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

U2 - 10.1145/380752.380818

DO - 10.1145/380752.380818

M3 - Conference article

AN - SCOPUS:0034826414

SN - 0734-9025

SP - 322

EP - 329

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 33rd Annual ACM Symposium on Theory of Computing

Y2 - 6 July 2001 through 8 July 2001

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