An O(n log n) algorithm for the voronoi diagram of a set of simple curve segments

Research output: Contribution to journalArticle

Abstract

Let X be a given set of n circular and straight line segments in the plane where two segments may interest only at their endpoints. We introduce a new technique that computes the Voronoi diagram of X in O(n log n) time. This result improves on several previous algorithms for special cases of the problem. The new algorithm is relatively simple, an important factor for the numerous practical applications of the Voronoi diagram.

Original languageEnglish (US)
Pages (from-to)365-393
Number of pages29
JournalDiscrete & Computational Geometry
Volume2
Issue number1
DOIs
StatePublished - Dec 1987

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'An O(n log n) algorithm for the voronoi diagram of a set of simple curve segments'. Together they form a unique fingerprint.

  • Cite this