de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44210

Burnikel,  Christoph
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45446

Seel,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

1999-1-007
(Any fulltext), 10KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Burnikel, C., Mehlhorn, K., & Seel, M.(1999). A simple way to recognize a correct Voronoi diagram of line segments (MPI-I-1999-1-007). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-6F7E-4
Abstract
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.