2024-03-28T22:06:24Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000325832023-04-27T10:00:04Z01164:02592:02707:02710
グラフの各辺両端点の小さい方の次数和に関する上限の初等的証明と幾何学問題への応用A Simple Proof of a Tight Bound of the Sum of Smaller Endpoint Degree over Edges of Graphs and Its Applications to Geometric Problemsjpnhttp://id.nii.ac.jp/1001/00032583/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32583&item_no=1&attribute_id=1&file_no=1Copyright (c) 1991 by the Information Processing Society of Japan機械技術研究所東京大学情報科学科東京大学情報科学科東京大学情報科学科日本IBM東京基礎研究所阿久津, 達也青木, 保一長谷川, 進今井, 浩徳山, 豪本稿ではまず、点集合V(|V|>),辺集合 E なる平面グラフ G=(,) について、[numerical formula]であること、および、この結果の最良性を示す。ここでdeg(υ)は、点υ∈Vの次数を意味する。さらに、長さ3のサイクルを持たない平面グラフにおいて、この和は高々4|E|?16となり、外平面グラフに対しては高々4|E|?12となることを証明する。次数和に関するこの性質は,ボロノイ図を扱う計算上ロバストなアルゴリズムの解析や、線分,曲線の交差を求める最適ランダム化アルゴリズムを得る上で有用である。In this paper we first show that, for a planar graph G=(V,E) with vertex set V(|V|≥14) and edge set E, [numerical formula] where deg(υ) is the degree of a vertex υ∈V, and that this is tight. Also, for a planar graph having no cycle of length 3, the summation is shown to be at most 4|E|-16, and for an outerplanar graph, at most 4|E|-12. This degree property can be used in the analysis of a computationally robust algorithm for Voronoi diagrams and also to obtain another optimal randomized algorithm for finding the intersections among line segments and curves.AN1009593X情報処理学会研究報告アルゴリズム(AL)199169(1991-AL-022)161991-07-222009-06-30