文献

J-GLOBAL ID：201802273281202966   整理番号：18A0184627

不動点定理を介したDelaunayグラフの特性化:単純証明

CHARACTERIZING DELAUNAY GRAPHS VIA FIXED POINT THEOREM: A SIMPLE PROOF

著者 (2件)： Matsui Tomomi (Tokyo Institute of Technology) ,  Miyamoto Yuichiro (Sophia University)
資料名： Journal of the Operations Research Society of Japan  (Journal of the Operations Research Society of Japan)
巻： 61  号： 1  ページ： 151-162(J-STAGE)  発行年： 2018年 
JST資料番号： G0402A  ISSN： 0453-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文は付与平面グラフがDelaunayグラフか否か,即ち,Delaunay三角形分割と位相同形か否かを決定する問題について議論した。Delaunayグラフを特性化し,幾つかの線形不等式系を解くことによってのみ問題の多項式時間アルゴリズムを生み出す定理が存在する。Hodgson,RivinとSmithにより提案された多項式時間アルゴリズムは,Rivinにより付与された線形不等式系を解き,それは双曲幾何に関する高度な議論に基づく。それとは独立して,Hiroshima,MiyamotoとSugiharaは別の線形不等式系と多項式時間アルゴリズムを付与した。彼らの議論はEuclid幾何の原始的議論に基づくが,不幸なことにそれらの証明は長く複雑である。本論文では,不動点定理用いてHiroshimaらにより示された定理の単純証明を付与した。(翻訳著者抄録)

シソーラス用語： *三角形分割 ,  *グラフ理論 ,  定理証明 ,  *不動点 ,  *線形計画法 ,  キャラクタリゼーション ,  等価性 ,  幾何学 ,  平面グラフ ,  不等式 ,  アルゴリズム ,  多項式 ,  計算理論 ,  組合せ問題
準シソーラス用語： Delaunay三角形分割 ,  Delaunayグラフ ,  線形不等式 ,  不動点定理 ,  特性化 ,  Euclid幾何 ,  多項式時間アルゴリズム

著者キーワード (4件)： Graph theory ,  Delaunay graph ,  fixed point theorem ,  linear programming

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (14件)：

• [1] F. Aurenhammer: Voronoi diagrams - a survey of a fundamental geometric data structure. ACM Computing Surveys, 23 (1991), 345-405.
• [2] L.E. Brouwer: Über Abbilidungen von Mannigfaltigkeiten. Mathematische Annalen, 71 (1912), 97-115.
• [3] M.B. Dillencourt and W.D. Smith: Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Mathematics, 161 (1996), 63-77.
• [4] H. Edelsbrunner: Algorithms in Combinatorial Geometry (Springer, Heidelberg, 1987).
• [5] T. Hiroshima, Y. Miyamoto, and K. Sugihara: Another proof of polynomial-time recognizability of Delaunay graphs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A (2000), 627-638.

タイトルに関連する用語 (4件)： 不動点定理 ,  グラフ ,  特性化 ,  証明