AN OPTIMAL BOUND FOR HIGH-QUALITY CONFORMING TRIANGULATIONS

Authors
TAN TS
Citation
Ts. Tan, AN OPTIMAL BOUND FOR HIGH-QUALITY CONFORMING TRIANGULATIONS, Discrete & computational geometry, 15(2), 1996, pp. 169-193
Citations number
21
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
15
Issue
2
Year of publication
1996
Pages
169 - 193
Database
ISI
SICI code
0179-5376(1996)15:2<169:AOBFHC>2.0.ZU;2-W
Abstract
This paper shows that, for any plane geometric graph G with n vertices , there is a triangulation T that conforms to G, i.e., each edge of G is the union of some edges of T, where T has O (n(2)) vertices with ea ch angle of its triangles measuring no more than 11/15 pi. Additionall y, T can be computed in O(n(2) log n) time.