Open Access System for Information Sharing

Login Library

 

Article
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

The minimum convex container of two convex polytopes under translations

Title
The minimum convex container of two convex polytopes under translations
Authors
Ahn, Hee-KapAbardia, JuditBae, Sang WonCheong, OtfriedDann, SusannaPark, DongwooShin, Chan-Su
Date Issued
Mar-2019
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
http://oasis.postech.ac.kr/handle/2014.oak/95280
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.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

 AHN, HEE KAP
Dept of Computer Science & Enginrg
Read more

Views & Downloads

Browse