AN UPPER BOUND FOR CONFORMING DELAUNAY TRIANGULATIONS

Authors
EDELSBRUNNER H TAN TS
Citation
H. Edelsbrunner et Ts. Tan, AN UPPER BOUND FOR CONFORMING DELAUNAY TRIANGULATIONS, Discrete & computational geometry, 10(2), 1993, pp. 197-213
Citations number
30
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, Pure","Computer Applications & Cybernetics",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
10
Issue
2
Year of publication
1993
Pages
197 - 213
Database
ISI
SICI code
0179-5376(1993)10:2<197:AUBFCD>2.0.ZU;2-N
Abstract
A plant geometric graph C in R2 conforms to another such graph G if ea ch edge of G is the union of some edges of C. It is proved that, for e very G with n vertices and m edges, there is a completion of a Delauna y triangulation of O(m2n) points that conforms to G. The algorithm tha t constructs the points is also described.