首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:CHARACTERIZING DELAUNAY GRAPHS VIA FIXED POINT THEOREM: A SIMPLE PROOF
  • 本地全文:下载
  • 作者:Tomomi Matsui ; Yuichiro Miyamoto
  • 期刊名称:日本オペレーションズ・リサーチ学会論文誌
  • 印刷版ISSN:0453-4514
  • 电子版ISSN:2188-8299
  • 出版年度:2018
  • 卷号:61
  • 期号:1
  • 页码:151-162
  • DOI:10.15807/jorsj.61.151
  • 语种:English
  • 出版社:Japan Science and Technology Information Aggregator, Electronic
  • 摘要:

    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.

  • 关键词:Graph theory;Delaunay graph;fixed point theorem;linear programming
国家哲学社会科学文献中心版权所有