MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments

MPI-I-1999-1-007

A simple way to recognize a correct Voronoi diagram of line segments

Burnikel, Christoph and Mehlhorn, Kurt and Seel, Michael

October 1999, 11 pages.

.
Status: available - back from printing

Writing a program for computing the Voronoi diagram of line segments is a complex task. Not only there is an abundance of geometric cases that have to be considered, but the problem is also numerically difficult. Therefore it is very easy to make subtle programming errors. In this paper we present a procedure that for a given set of sites $S$ and a candidate graph $G$ rigorously checks that $G$ is the correct Voronoi diagram of line segments for $S$. Our procedure is particularly efficient and simple to implement.

  • MPI-I-1999-1-007.ps
  • Attachement: MPI-I-1999-1-007.ps (257 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1999-1-007

Hide details for BibTeXBibTeX
@TECHREPORT{BurnikelMehlhornSeel99,
  AUTHOR = {Burnikel, Christoph and Mehlhorn, Kurt and Seel, Michael},
  TITLE = {A simple way to recognize a correct Voronoi diagram of line segments},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-1999-1-007},
  MONTH = {October},
  YEAR = {1999},
  ISSN = {0946-011X},
}