Skip to main navigation Skip to search Skip to main content

PVD1: A stable implementation for computing voronoi diagrams of polygonal pockets

  • Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

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.

Original languageEnglish
Title of host publicationAlgorithm Engineering and Experimentation - 3rd International Workshop, ALENEX 2001, Revised Papers
EditorsAdam L. Buchsbaum, Jack Snoeyink
PublisherSpringer Verlag
Pages105-116
Number of pages12
ISBN (Print)3540425608, 9783540425601
DOIs
StatePublished - 2001
Event3rd International Workshop on Algorithm Engineering and Experimentation, ALENEX 2001 - Washington, United States
Duration: Jan 5 2001 → Jan 6 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2153
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Workshop on Algorithm Engineering and Experimentation, ALENEX 2001
Country/TerritoryUnited States
CityWashington
Period01/5/01 → 01/6/01

Fingerprint

Dive into the research topics of 'PVD1: A stable implementation for computing voronoi diagrams of polygonal pockets'. Together they form a unique fingerprint.

Cite this