Art

J-GLOBAL ID：201802273281202966   Reference number：18A0184627

CHARACTERIZING DELAUNAY GRAPHS VIA FIXED POINT THEOREM: A SIMPLE PROOF

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

Author (2)： Matsui Tomomi (Tokyo Institute of Technology) ,  Miyamoto Yuichiro (Sophia University)
Material： Journal of the Operations Research Society of Japan  (日本オペレーションズ・リサーチ学会論文誌)
Volume： 61  Issue： 1  Page： 151-162(J-STAGE)  Publication year： 2018 
JST Material Number： G0402A  ISSN： 0453-4514  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *triangulation (mathematics) ,  *graph theory ,  theorem proving ,  *fixed point (mathematics) ,  *linear programming ,  characterization ,  equivalency ,  geometry ,  planar graph ,  inequality ,  algorithm ,  polynomial ,  computation theory ,  combinational problem ,  fixed point theorem ,  Euclidean geometry
Semi thesaurus term： Delaunay triangulation partitioning ,  Delaunayグラフ ,  線形不等式 ,  characterization ,  polynomial time algorithm

Author keywords (4)： Graph theory ,  Delaunay graph ,  fixed point theorem ,  linear programming

JST classification (2)： Theory of computation  (JB02000A) ,  Basics of graph theory  (IA02020S)

Reference (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.

Terms in the title (4)： 不動点定理 ,  グラフ ,  特性化 ,  証明