論文

査読有り
1999年3月

Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN
  • K Imai
  • ,
  • H Imai
  • ,
  • T Tokuyama

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000079241500004&DestApp=WOS_CPL
ID情報
  • ISSN : 0453-4514
  • Web of Science ID : WOS:000079241500004

エクスポート
BibTeX RIS