@inproceedings{b8d20ca59f8d4f1d9f6c6e820c71e694,
title = "PVD1: A stable implementation for computing voronoi diagrams of polygonal pockets",
abstract = "Voronoi diagrams of pockets, i.e. polygons with holes, have a variety of important applications but are particularly challenging to compute robustly. We report on an implementation of a simple algorithm which does not rely on exact arithmetic to achieve robustness; rather, it achieves its robustness through carefully engineered handling of geometric predicates. Although we do not give theoretical guarantees for robustness or accuracy, the software has sustained extensive experimentation (on real and simulated data) and day-to-day usage on real-world data. The algorithm is shown experimentally to compare favorably in running time with prior methods.",
author = "Saurabh Sethia and Martin Held and Mitchell, \{Joseph S.B.\}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 3rd International Workshop on Algorithm Engineering and Experimentation, ALENEX 2001 ; Conference date: 05-01-2001 Through 06-01-2001",
year = "2001",
doi = "10.1007/3-540-44808-x\_8",
language = "English",
isbn = "3540425608",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "105--116",
editor = "Buchsbaum, \{Adam L.\} and Jack Snoeyink",
booktitle = "Algorithm Engineering and Experimentation - 3rd International Workshop, ALENEX 2001, Revised Papers",
}