平面グラフが凸図形のVoronoi図であることの確認法

• Item type: SIG Technical Reports(1)
• 公開日: 2005-01-20
• タイトル: 平面グラフが凸図形のVoronoi図であることの確認法
• タイトル / 言語: en
• タイトル: How to Confirm that a planar Graph is a Voronoi Diagram for Convex Objects
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 和歌山大学・システム工学部
• 著者所属(英): en
• 著者所属(英): Wakayama University, Faculty of Systems Engineering
• 著者名: 今井, 敏行
• 著者名(英): Toshiyuki, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 図形処理において，近似アルゴリズムの実装や，厳密アルゴリズムの計算誤差のある実装では，出力図形が正しいかどうかはわからない．点のVoronoi図の構成においては，点のVoronoi図の双対であるDelaunay図に関する定理があり，それを用いて局所的な判定で真のVoronoi図であるか確認できる．本稿では，この定理を拡張し凸図形のVoronoi図の構成に適用できるようにし，その証明を与える．この定理により，凸図形のVoronoi図に構成に関して，近似アルゴリズムを利用して厳密解を求められるようになる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In Geonometric processing, implementations of approximated algorithms or those of exact algorithms with numerical errors do not guarantee the the correctness of the output. For the construction of voronoi diagrams for points, a theorem related to the Delaunay diagram, which is the dual of the Voronoi diagram for points, gives us a local test to confirm that the output is the correct Voronoi diagram. In this paper, the theorem is extended to apply to the construction of the Voronoi diagrams for convex objects and the proof is given. This theorem allows us to obtain the correct Voronoi diagram for some convex objects by using an approximated algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 5(2004-AL-099), p. 15-22, 発行日 2005-01-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会