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 :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2778244
بازگشت