不動点定理によるドロネー性の確認
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 2012-10-26
著者
-
松井 知己
中央大学理工学部
-
松井 知己
東京大学大学院工学系研究科計数工学専攻
-
松井 知己
東京大学工学系研究科
-
Tomomi Matsui
Chuo University
-
Yuichiro Miyamoto
Sophia University
-
松井 知己
東京大学 大学院情報理工学系研究科
-
Tomomi Matsui
Department of Information and System Engineering, Chuo University
関連論文
- 古典的オーヴァーハングパズルをLPで解く(ORメモランダム)
- 木における消防士問題に対する近似アルゴリズムの改良 (コンピュテーション)
- パズル・ゲームに見る悪魔の証明
- スポーツスケジューリング
- 木における消防士問題に対する近似アルゴリズムの改良
- 統計的機械翻訳におけるフレーズ対応最適化を利用したN-best翻訳候補のリランキング
- オークションの設計理論とOR(2)(数理計画の理論と実装)
- 数理計画の理論と実装 : オークションの設計理論とOR(1)(ネットワークシステムのセキュリティ評価と危機管理)
- フルートの運指のモデル化とその最適化に関する研究
- 1-C-8 ハブ空港配置問題の近似解法(離散最適化(1))