Intersecting is easier than sorting

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

This paper settles a long-standing open question of computational geometry: Is it possible to compute all k intersections between n arbitrary line segments in time linear in k? We answer this question affirmatively by presenting the first algorithm with a running time of the form O(k+f(n)), where I is a sub quadratic function of n. The function f we achieve is actually quasi-linear in n, which makes our algorithm the most efficient to date for each value of k. To obtain this result we must turn away from traditional, sweep-line-based schemes. Instead, we introduce a new hierarchical strategy for dealing with segments without ever reducing the dimensionality of the problem. This framework is used to solve other related problems. In particular, we are able to present the first subquadratic algorithm for computing intersections (as opposed to reporting each of them explicitly}, and we give the first optimal algorithm for computing the intersections of a line arrangement with a query segment. Using duality arguments we also present an improved algorithm for a point enclosure problem.

Original languageEnglish (US)
Title of host publicationProceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984
PublisherAssociation for Computing Machinery
Pages125-134
Number of pages10
ISBN (Electronic)0897911334
DOIs
StatePublished - Dec 1 1984
Externally publishedYes
Event16th Annual ACM Symposium on Theory of Computing, STOC 1984 - Washington, United States
Duration: Apr 30 1984May 2 1984

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other16th Annual ACM Symposium on Theory of Computing, STOC 1984
CountryUnited States
CityWashington
Period4/30/845/2/84

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Intersecting is easier than sorting'. Together they form a unique fingerprint.

  • Cite this

    Chaselle, B. (1984). Intersecting is easier than sorting. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984 (pp. 125-134). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800057.808674