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

MPI-I-1999-1-007. October 1999, 11 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	257 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

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

BibTeX
@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},}