DocumentCode
2778244
Title
Triangulating a simple polygon in linear time
Author
Chazelle, Bernard
Author_Institution
Dept. of Comput. Sci., Princeton Univ., NJ, USA
fYear
1990
fDate
22-24 Oct 1990
Firstpage
220
Abstract
A linear-time deterministic algorithm for triangulating a simple polygon is developed. The algorithm is elementary in that it does not require the use of any complicated data structures; in particular, it does not need dynamic search trees, finger trees, or fancy point location structures
Keywords
computational complexity; computational geometry; data structures; 2D computational geometry; conformality; data structures; granularity; linear-time deterministic algorithm; merging; simple polygon; triangulation; visibility maps; Computer graphics; Fingers; Merging; Partitioning algorithms; Polynomials; Sorting; Tree data structures; Turning;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location
St. Louis, MO
Print_ISBN
0-8186-2082-X
Type
conf
DOI
10.1109/FSCS.1990.89541
Filename
89541
Link To Document