点ボロノイ図を利用した 線分ボロノイ図の位相構造決定法

• Item type: SIG Technical Reports(1)
• 公開日: 2005-01-20
• タイトル: 点ボロノイ図を利用した 線分ボロノイ図の位相構造決定法
• タイトル / 言語: en
• タイトル: A Method for Determining the Topological Structure of Voronoi Diagram for Segments by Using Voronoi Diagram for Points.
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 和歌山大学大学院 システム工学研究科
• 著者所属: 和歌山大学 システム工学部
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems Engineering, Wakayama University
• 著者所属(英): en
• 著者所属(英): Faculty of Systems Engineering, Wakayama University
• 著者名: 渡辺, 秀臣; 今井, 敏行
• 著者名(英): Hideomi, Watanabe; Toshiyuki, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 与えられた線分をいくつかの点に置き換えて、その点ボロノイ図から線分ボロノイ図を近似構成する事ができる。しかし、本来の線分ボロノイ図の位相構造と同じである事を保証した近似構成法はまだなかった。そこで本稿では、線分を両端点に置き換え線分上に点を追加して逐次的に近似構成していくと同時に、各ボロノイ辺を調べる事で本来の位相構造と同じであるかどうかを判定し、近似構成での線分ボロノイ図の位相構造を決定する方法について述べる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An approximate Voronoi diagram for segments can be constructed from the Voronoi diagram for points by replacing each segments with some points. There is no algorithm for approximate construction which guarantees that the topological structure of approximated diagram is exactly the same as the original Voronoi diagram for segments. This paper describes how to determine the topological structure of a Voronoi diagram for segments from the approximated one. First, all segments are replaced with the endpoints to construct the initial approximate Voronoi diagram for the endpoints and then the diagram is modified by adding internal points of the segments in certain manner until it is judged that the approximate diagram has the same topological structure as the original Voronoi diagram only by investigating Voronoi edges of the approximated diagram.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 5(2004-AL-099), p. 7-14, 発行日 2005-01-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会