An Easy to Use Implementation of Linear Perturbations within CGAL

Comes, Jochen; Ziegelmann, Mark

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

An Easy to Use Implementation of Linear Perturbations within CGAL

MPS-Authors

/persons/resource/persons45802

Ziegelmann, Mark
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)

There are no public fulltexts stored in PuRe

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: https://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.