不動点定理によるドロネー性の確認

• Item type: SIG Technical Reports(1)
• 公開日: 2012-10-26
• タイトル: 不動点定理によるドロネー性の確認
• タイトル / 言語: en
• タイトル: Characterizing Delaunay Graphs via Fixed Point Theorem
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Chuo University
• 著者所属: Sophia University
• 著者所属(英): en
• 著者所属(英): Chuo University
• 著者所属(英): en
• 著者所属(英): Sophia University
• 著者名: Tomomi, Matsui; Yuichiro, Miyamoto
• 著者名(英): Tomomi, Matsui; Yuichiro, Miyamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper discusses a problem for determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. There exists a theorem which characterizes Delaunay graphs and yields a polynomial time algorithm for the problem only by solving a certain linear inequality system. The theorem was proved by Rivin based on arguments of hyperbolic geometry. Independently, Hiroshima, Miyamoto and Sugihara gave another proof of the theorem based on primitive arguments on Euclidean geometry. Unfortunately, the existing proofs of the theorem are rather difficult or long. In this paper, we give a simple proof of the theorem characterizing Delaunay graphs, which is based on the fixed point theorem.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper discusses a problem for determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. There exists a theorem which characterizes Delaunay graphs and yields a polynomial time algorithm for the problem only by solving a certain linear inequality system. The theorem was proved by Rivin based on arguments of hyperbolic geometry. Independently, Hiroshima, Miyamoto and Sugihara gave another proof of the theorem based on primitive arguments on Euclidean geometry. Unfortunately, the existing proofs of the theorem are rather difficult or long. In this paper, we give a simple proof of the theorem characterizing Delaunay graphs, which is based on the fixed point theorem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2012-AL-142, 号 1, p. 1-6, 発行日 2012-10-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会