An elementary algorithm for reporting intersections of red/blue curve segments

Jean Daniel Boissonnat, Antoine Vigneron

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Let ET and £b be two sets of Ar-monotone and non-intersecting curve segments, E = £r U £b and |£| -n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(;i log« + and log log«) and it requires O(«) space.

Original languageEnglish (US)
Pages (from-to)167-175
Number of pages9
JournalComputational Geometry: Theory and Applications
Volume21
Issue number3
DOIs
StatePublished - Jan 1 2002

Keywords

  • Computational geometry
  • Plane sweep
  • Robust algorithms
  • Segment intersection

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'An elementary algorithm for reporting intersections of red/blue curve segments'. Together they form a unique fingerprint.

Cite this