Bundling two simple polygons to minimize their convex hull
SCIE
SCOPUS
- Title
- Bundling two simple polygons to minimize their convex hull
- Authors
- Choi, J.; Park, D.; Ahn, H.-K.
- Date Issued
- 2017-02
- Publisher
- Springer Verlag
- Abstract
- Given two simple polygons P and Q in the plane, we study the problem of finding a placement ?P of P such that ?P and Q are disjoint in their interiors and the convex hull of their union is minimized. We present exact algorithms for this problem that use much less space than the complexity of the Minkowski sum of P and Q. When the orientation of P is fixed, we find an optimal translation of P in O(n2m2 log n) time using O(nm) space, where n and m (n �� m) denote the number of edges of P and Q, respectively. When we allow reorienting P, we find an optimal rigid motion of P in O(n3m3 log n) time using O(nm) space. In both cases, we find an optimal placement of P using linear space at the expense of slightly increased running time. For two polyhedra in three dimensional space, we find an optimal translation in O(n3m3 log n) time using O(nm) space or in O(n3m3(m + log n)) time using linear space. ? Springer International Publishing AG 2017.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/105429
- DOI
- 10.1007/978-3-319-53925-6_6
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10167 LNCS, page. 66 - 77, 2017-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.