An Optimal Algorithm for Intersecting Line Segments in the Plane

Bernard Chazelle, Herbert Edelsbrunner

Research output: Contribution to journalArticlepeer-review

233 Scopus citations

Abstract

The main contribution of this work is an O1992-time algorithm for computing all k intersections among n line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of n + k in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.

Original languageEnglish (US)
Pages (from-to)1-54
Number of pages54
JournalJournal of the ACM (JACM)
Volume39
Issue number1
DOIs
StatePublished - Feb 1 1992

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'An Optimal Algorithm for Intersecting Line Segments in the Plane'. Together they form a unique fingerprint.

Cite this