Optimal algorithm for intersecting line segments in the plane

Bernard Chazelle, Herbert Edelsbrunner

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

47 Scopus citations

Abstract

The authors present the first optimal algorithm for the following problem: given n line segments in the plane, computes all k pairwise intersections in O(n log n + k) time. Within the same asymptotic cost the algorithm will also compute the adjacencies of the planar subdivision induced by the segments, which is a useful data structure for contour-filling on raster devices.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages590-600
Number of pages11
ISBN (Print)0818608773, 9780818608773
DOIs
StatePublished - 1988

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Optimal algorithm for intersecting line segments in the plane'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Edelsbrunner, H. (1988). Optimal algorithm for intersecting line segments in the plane. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 590-600). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1988.21975