Another Proof of Polynomial-Time Recognizability of Delaunay Graphs

Tetsuya HIROSHIMA; Yuichiro MIYAMOTO; Kokichi SUGIHARA

Another Proof of Polynomial-Time Recognizability of Delaunay Graphs

Tetsuya HIROSHIMA, Yuichiro MIYAMOTO, Kokichi SUGIHARA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.627-638

Publication Date: 2000/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Tetsuya HIROSHIMA, Yuichiro MIYAMOTO, Kokichi SUGIHARA, "Another Proof of Polynomial-Time Recognizability of Delaunay Graphs" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 4, pp. 627-638, April 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_627/_p

Copy

@ARTICLE{e83-a_4_627,
author={Tetsuya HIROSHIMA, Yuichiro MIYAMOTO, Kokichi SUGIHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Another Proof of Polynomial-Time Recognizability of Delaunay Graphs},
year={2000},
volume={E83-A},
number={4},
pages={627-638},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Another Proof of Polynomial-Time Recognizability of Delaunay Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 627
EP - 638
AU - Tetsuya HIROSHIMA
AU - Yuichiro MIYAMOTO
AU - Kokichi SUGIHARA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - 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.
ER -