Aligning Two Convex Figures to Minimize Area or Perimeter
SCIE
SCOPUS
- Title
- Aligning Two Convex Figures to Minimize Area or Perimeter
- Authors
- Ahn, HK; Cheong, O
- Date Issued
- 2012-02
- Publisher
- SPRINGER
- Abstract
- Given two compact convex sets P and Q in the plane, we consider the problem of finding a placement I center dot P of P that minimizes the convex hull of I center dot Pa(a)Q. We study eight versions of the problem: we consider minimizing either the area or the perimeter of the convex hull; we either allow I center dot P and Q to intersect or we restrict their interiors to remain disjoint; and we either allow reorienting P or require its orientation to be fixed. In the case without reorientations, we achieve exact near-linear time algorithms for all versions of the problem. In the case with reorientations, we compute a (1+epsilon)-approximation in time O(epsilon (-1/2)log n+epsilon (-3/2)log (a) (1/epsilon)) if the two sets are convex polygons with n vertices in total, where aa{0,1,2} depending on the version of the problem.
- Keywords
- Computational geometry; Optimization; Convex hull; Area; Perimeter; MAXIMUM OVERLAP; POLYGONS; PACKING; TRANSLATIONS; SETS; HULL
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/16627
- DOI
- 10.1007/S00453-010-9466-1
- ISSN
- 0178-4617
- Article Type
- Article
- Citation
- ALGORITHMICA, vol. 62, no. 1-2, page. 464 - 479, 2012-02
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.