DocumentCode
2233370
Title
Stable maintenance of point set triangulations in two dimensions
Author
Fortune, Steven
Author_Institution
AT&T Bell Labs., Murray Hill, NJ, USA
fYear
1989
fDate
30 Oct-1 Nov 1989
Firstpage
494
Lastpage
499
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
computational geometry; digital arithmetic; error analysis; stability; epsilon arithmetic; geometric problems; line arrangements; plane; point set triangulations; stability; stable algorithms; two-dimensional convex hulls; Error analysis; Floating-point arithmetic; Numerical analysis; Numerical stability; Polynomials; Robust stability; Robustness; Testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location
Research Triangle Park, NC
Print_ISBN
0-8186-1982-1
Type
conf
DOI
10.1109/SFCS.1989.63524
Filename
63524
Link To Document