An upper bound for conforming Delaunay triangulations |
| |
Authors: | Herbert Edelsbrunner Tiow Seng Tan |
| |
Institution: | (1) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA;(2) Department of Information Systems and Computer Science, National University of Singapore, Republic of Singapore |
| |
Abstract: | A plane geometric graphC in ℝ2
conforms to another such graphG if each edge ofG is the union of some edges ofC. It is proved that, for everyG withn vertices andm edges, there is a completion of a Delaunay triangulation ofO(m
2
n) points that conforms toG. The algorithm that constructs the points is also described.
Research of the first author is supported by the National Science Foundation under Grant CCR-8921421 and under the Alan T.
Waterman award, Grant CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication
are those of the authors and do not necessarily reflect the view of the National Science Foundation. Work of the second author
was conducted while he was on study leave at the University of Illinois. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|