論文

査読有り
2011年12月

AN APPROXIMATION ALGORITHM FOR LOCATING MAXIMAL DISKS WITHIN CONVEX POLYGONS

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
  • Hirofumi Aota
  • ,
  • Takuro Fukunaga
  • ,
  • Hiroshi Nagamochi

21
6
開始ページ
661
終了ページ
684
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1142/S0218195911003858
出版者・発行元
WORLD SCIENTIFIC PUBL CO PTE LTD

This paper considers a problem of locating the given number of disks into a container no that the area covered by the disks is maximized. In the problem, the radii of the disks can be changed arbitrarily unless they overlap outside of the container, and the disks are allowed to overlap with each other. We present an approximation algorithm for this problem assuming that the container is a convex polygon. Our algorithm achieves approximation ratio (0.78 - epsilon) for any small epsilon > 0. Since the computation tine of our algorithm depends on the number of corners of the convex polygon exponentially, we also give a heuristic to reduce the number of corners.

リンク情報
DOI
https://doi.org/10.1142/S0218195911003858
DBLP
https://dblp.uni-trier.de/rec/journals/ijcga/AotaFN11
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000300235000004&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/journals/ijcga/ijcga21.html#journals/ijcga/AotaFN11
ID情報
  • DOI : 10.1142/S0218195911003858
  • ISSN : 0218-1959
  • DBLP ID : journals/ijcga/AotaFN11
  • Web of Science ID : WOS:000300235000004

エクスポート
BibTeX RIS