Home >

news Help

Publication Information


Title
Japanese: 
English:Characterizing Delaunay graphs via fixed point theorem: a simple proof 
Author
Japanese: 松井知己, 宮本 裕一郎.  
English: Tomomi Matsui, Yuichiro Miyamoto.  
Language English 
Journal/Book name
Japanese:日本オペレーションズ・リサーチ学会論文誌 
English:Journal of the Operations Research Society of Japan 
Volume, Number, Page Vol. 61    No. 1    pp. 151-162
Published date Jan. 7, 2018 
Publisher
Japanese:公益社団法人 日本オペレーションズ・リサーチ学会 
English:Operations Research Society of Japan 
Conference name
Japanese: 
English: 
Conference site
Japanese: 
English: 
File
Official URL https://www.jstage.jst.go.jp/article/jorsj/61/1/61_151/_article
 
DOI https://doi.org/10.15807/jorsj.61.151
Abstract This paper discusses the problem of determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. There exist theorems which characterize Delaunay graphs and yield polynomial time algorithms for the problem only by solving some linear inequality systems. A polynomial time algorithm proposed by Hodgson, Rivin and Smith solves a linear inequality system given by Rivin, which is based on sophisticated arguments about hyperbolic geometry. Independently, Hiroshima, Miyamoto and Sugihara gave another linear inequality system and a polynomial time algorithm. Although their discussion is based on primitive arguments on Euclidean geometry, their proofs are long and intricate, unfortunately. In this paper, we give a simple proof of the theorem shown by Hiroshima et al. by employing the fixed point theorem.

©2007 Tokyo Institute of Technology All rights reserved.