STACKING AND BUNDLING TWO CONVEX POLYGONS
SCIE
SCOPUS
- Title
- STACKING AND BUNDLING TWO CONVEX POLYGONS
- Authors
- Ahn, HK; Cheong, O
- Date Issued
- 2005-12
- Publisher
- SPRINGER-VERLAG BERLIN
- Abstract
- Given two compact convex sets C-1 and C-2 in the plane, we consider the problem of finding a placement phi C-1 of C-1 that minimizes the area of the convex hull of phi C-1 boolean OR C-2. We first consider the case where phi C-1 and C-2 are allowed to intersect (as in "stacking" two flat objects in a convex box), and then add the restriction that their interior has to remain disjoint (as when "bundling" two convex objects together into a tight bundle). In both cases, we consider both the case where we are allowed to reorient C-1, and where the orientation is fixed. In the case without reorientations, we achieve exact near-linear time algorithms, in the case with reorientations we compute a (1 + epsilon)-approximation in time O(epsilon(-1/2) log n+epsilon(-3/2) log epsilon(-1/2)), if two sets are convex polygons with n vertices in total.
- Keywords
- OVERLAP
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/28556
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- LECTURE NOTES ON COMPUTER SCIENCE, vol. 3827, page. 40 - 49, 2005-12
- 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.