How to Compute the Voronoi Diagram of Line Segments: Theoretical and Experimental Results
Lists
Only you see this
Abstract
Given a set of non-intersecting (except at endpoints) line segments in the plane we want to compute their Voronoi diagram. Although there are several algorithms for this problem in the literature [Yap87, For87, CS89, BDS+92, KMM90] nobody claims to have a correct implementation. This is due to the fact that the algorithms presuppose exact arithmetic and that the Voronoi diagram of segments requires to compute with non-rational algebraic numbers. We report about a detailed study of the numerical precision required for evaluating the geometric test exactly and about first experimental experiences. More specifically, we improve the precision bound implied by classical root separation results by more than two orders of magnitude and we compare the implementation strategies suggested by our theoretical results.
BibTeX
@inproceedings{burnikel1994how,
author = {Christoph Burnikel and Kurt Mehlhorn and Stefan Schirra},
title = {{How to Compute the Voronoi Diagram of Line Segments: Theoretical and Experimental Results}},
booktitle = {ESA},
year = {1994},
url = {https://openreview.net/forum?id=lk7x1SEHgb},
}Loading related content...