Another Proof of Polynomial-Time Recognizability of Delaunay Graphs(Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
This paper presents a new proof to a polynomial-time algorithm for determining whether a given embedded graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. The problem of recognizing the Delaunay graph had long been open. Recently Hodgson et al. gave a combinatorial characterization of the Delaunay graph, and thus constructed the polynomial-time algorithm for recognizing the Delaunay graphs. Their proof is based on sophisticated discussions on hyperbolic geometry. On the other hand, this paper gives another and simpler proof based on primitive arguments on Euclidean geometry. Moreover, the algorithm is applied to study the distribution of non-Delaunay graphs.
- 2000-04-25
著者
-
Miyamoto Yuichiro
The Authors Are With The Department Of Mathematical Engineering And Information Physics The Universi
-
Sugihara K
Univ. Tokyo Tokyo Jpn
-
Sugihara Kokichi
The Authors Are With The Department Of Mathematical Engineering And Information Physics The Universi
-
HIROSHIMA Tetsuya
The authors are with the Department of Mathematical Engineering and Information Physics, The Univers
-
Hiroshima Tetsuya
The Authors Are With The Department Of Mathematical Engineering And Information Physics The Universi
関連論文
- Another Proof of Polynomial-Time Recognizability of Delaunay Graphs(Special Section on Discrete Mathematics and Its Applications)
- An Experimental System for Generating Polyhedral Structures from Line Drawings