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

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

An Easy to Use Implementation of Linear Perturbations within CGAL

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

Ziegelmann,  Mark
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Comes, J., & Ziegelmann, M. (1999). An Easy to Use Implementation of Linear Perturbations within CGAL. In J. S. Vitter, & C. D. Zaroliagis (Eds.), Algorithm engineering (WAE-99): 3rd International Workshop, WAE'99 (pp. 169-182). Berlin: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-3596-9
Abstract
Most geometric algorithms are formulated under the non-degeneracy assumption which usually does not hold in practice. When implementing such an algorithm, a treatment of degenerate cases is necessary to prevent incorrect outputs or crashes. One way to overcome this nontrivial task is to use perturbations. In this paper we describe a generic implementation of efficient random linear perturbations within CGAL and discuss the practicality of using it examining the convex hull problem, line segment intersection and Delaunay triangulation.