1999年3月
Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN
- ,
- ,
- 巻
- 42
- 号
- 1
- 開始ページ
- 45
- 終了ページ
- 58
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- 出版者・発行元
- OPERATIONS RES SOC JAPAN
This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduces 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(4)n lambda(16)(mn) log mn)time, where m and n are the numbers of edges of P and Q, respectively, and lambda(16)(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in O(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximin manner is also considered.
- リンク情報
- ID情報
-
- ISSN : 0453-4514
- Web of Science ID : WOS:000079241500004