English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

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

MPS-Authors
/persons/resource/persons44210

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

/persons/resource/persons45021

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

/persons/resource/persons45446

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
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: https://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.