ABSTRACT
To make geometric computation robust against numerical errors is one of the most important issues for practical applications of geometric algorithms. We first review existing approaches to robust geometric computation, and next show that there still remain many difficulties. Finally we discuss possible directions to overcome these difficulties and thus to achieve superrobustness.
- Mehlhorn, K., and Naher, S. 1999. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press. Google ScholarDigital Library
- Sugihara, K., and Iri, M. 1989. A solid modelling system free from topological inconsistency. Journal of Information Processing 12, 4, 380--393. Google ScholarDigital Library
- Sugihara, K., and Iri, M. 1992. Construction of the voronoi diagram for one million generators in single-precision arithmetic. Proceedings of the IEEE 80, 9, 1471--1484.Google ScholarCross Ref
- Sugihara, K. 1999. Resolvable representation of polyhedra. Discrete and Computational Geometry 21, 243--255.Google ScholarCross Ref
- Sugihara, K. 2007. Sliver-free perturbation for the delaunay tetrahedrization. Computer-Aided Design 39, 87--94. Google ScholarDigital Library
- Yap, C. K. 1997. Toward exact geometric computation. Computational Geometry: Theory and Applications 7, 3--23. Google ScholarDigital Library
Index Terms
- Toward superrobust geometric computation
Recommendations
An exact, complete and efficient computation of arrangements of Bézier curves
SPM '07: Proceedings of the 2007 ACM symposium on Solid and physical modelingArrangements of planar curves are fundamental structures in computational geometry. The arrangement package of CGAL can construct and maintain arrangements of various families of curves, when provided with the representation of the curves and some basic ...
LOOK: A Lazy Object-Oriented Kernel design for geometric computation
In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the exact number types provided by LEDA allowing for ...
Exact computation of the medial axis of a polyhedron
We present an accurate algorithm to compute the internal Voronoi diagram and medial axis of a 3-D polyhedron. It uses exact arithmetic and exact representations for accurate computation of the medial axis. The algorithm works by recursively finding ...
Comments