Euclid距離による多角形配置問題とそれに関連する動的Voronoi図について

• Item type: SIG Technical Reports(1)
• 公開日: 1990-05-17
• タイトル: Euclid距離による多角形配置問題とそれに関連する動的Voronoi図について
• タイトル / 言語: en
• タイトル: Euclidean Maximin Location of Convex Objects in a Polygon and Related Dynamic Voronoi Diagrams
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州工業大学・情報科学センター
• 著者所属: 日本IBM東京基礎研究所
• 著者所属(英): en
• 著者所属(英): Information Science Center, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): IBM Research, Tokyo Research Laboratory
• 著者名: 今井, 桂子; 徳山, 豪
• 著者名(英): Keiko, Imai; Takeshi, Tokuyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，与えられた凸多角形Pを他の多角形Qの内部に最適に，すなわち，PとQの相対Euclid距離が最小になるように配置する問題を考える。P?Euclid Voronoi図と呼ばれる新しいVoronoi図を定義し，その動的な変化を考える事により，種々の問題に効率の良い算法が得られる。特に，Pがm角形，Qがn角形のときに，Pを回転と平行移動で動かす時，O（^4nλ_<16>（）log )時間で最適配置が求まる。ここでλ_<16>（）は，N文字の16次Davenport?Shinzel列の長さで，ほとんど線形な関数である。更に，Pがk個の連結成分を持ち，平行移動する場合も取り扱う。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in O(m^4nλ_<16>(mn)log mn) time, where m and n are the numbers of edges of P and Q, respectively, and λ_<16>(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. The problem of placing multiple translates of P inside Q in a maximin manner is also considered, an in connection with this problem the dynamic Voronoi diagram of k rigidly moving sets of n points is investigated.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1990, 号 37(1990-AL-015), p. 1-8, 発行日 1990-05-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会