The minimum convex container of two convex polytopes under translations
SCIE
SCOPUS
- Title
- The minimum convex container of two convex polytopes under translations
- Authors
- Ahn, Hee-Kap; Abardia, Judit; Bae, Sang Won; Cheong, Otfried; Dann, Susanna; Park, Dongwoo; Shin, Chan-Su
- Date Issued
- 2019-03
- Publisher
- ELSEVIER SCIENCE BV
- Abstract
- Given two convex d-polytopes P and Q in R-d for d >= 3, we study the problem of bundling P and Q in a smallest convex container. More precisely, our problem asks to find a minimum convex set containing P and a translate of Q that do not properly overlap each other. We present the first exact algorithm for the problem for any fixed dimension d 3. The running time is O(n((d-1)[d+1]/2)), where n denotes the number of vertices of P and Q. In particular, in dimension d = 3, our algorithm runs in O(n(4)) time. We also give an example of polytopes P and Q such that in the smallest container the translates of P and Q do not touch. (C) 2018 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/95280
- DOI
- 10.1016/j.comgeo.2018.02.004
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, vol. 77, page. 40 - 50, 2019-03
- 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.