A LINEAR-TIME NEAR-OPTIMUM-LENGTH TRIANGULATION ALGORITHM FOR CONVEX POLYGONS

Authors
KANTABUTRA V
Citation
V. Kantabutra, A LINEAR-TIME NEAR-OPTIMUM-LENGTH TRIANGULATION ALGORITHM FOR CONVEX POLYGONS, Journal of computer and system sciences, 49(2), 1994, pp. 325-333
Citations number
2
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences → ACNP
ISSN journal
00220000
Volume
49
Issue
2
Year of publication
1994
Pages
325 - 333
Database
ISI
SICI code
0022-0000(1994)49:2<325:ALNTAF>2.0.ZU;2-T
Abstract
This paper shows how to compute a short triangulation for a convex pol ygon in O(n) time, where n is the number of sides of the input polygon . The resulting triangulation is guaranteed to be of a total length th at is only a constant factor of the shortest possible. (C) 1994 Academ ic Press, Inc.