Stable maintenance of point set triangulations in two dimensions
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 494-499
- https://doi.org/10.1109/sfcs.1989.63524
Abstract
Geometric algorithms are explored, assuming that arithmetic is done approximately. Stable algorithms are described for two geometric problems. The first algorithm computes two-dimensional convex hulls. The main result is that a triangulation of a set of points in the plane can be maintained stably. The second algorithm deals with line arrangements in the plane.Keywords
This publication has 9 references indexed in Scilit:
- An efficient algorith for determining the convex hull of a finite planar setPublished by Elsevier ,2002
- The problems of accuracy and robustness in geometric computationComputer, 1989
- Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmeticPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Towards implementing robust geometric computationsPublished by Association for Computing Machinery (ACM) ,1988
- Some algebraic and geometric computations in PSPACEPublished by Association for Computing Machinery (ACM) ,1988
- The universality theorems on the classification problem of configuration varieties and convex polytopes varietiesPublished by Springer Nature ,1988
- Finite-resolution computational geometryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Planarity and duality of finite and infinite graphsJournal of Combinatorial Theory, Series B, 1980