Overlap of convex polytopes under rigid motion
SCIE
SCOPUS
- Title
- Overlap of convex polytopes under rigid motion
- Authors
- Ahn, HK; Siu-Wing Cheng; Hyuk Jun Kweon; Juyoung Yon
- Date Issued
- 2014-01
- Publisher
- Elsevier BV
- Abstract
- We present an algorithm to compute a rigid motion that approximately maximizes the volume of the intersection of two convex polytopes P-1 and P-2 in R-3. For all epsilon is an element of (0, 1/2] and for all n >= 1/epsilon, our algorithm runs in O(epsilon(-3) n log(3.5) n) time with probability 1 - n(-O(1)). The volume of the intersection guaranteed by the output rigid motion is a (1 - epsilon)-approximation of the optimum, provided that the optimum is at least lambda . max{vertical bar P-1 vertical bar . vertical bar P-2 vertical bar} for some given constant lambda is an element of (0, 1]. (C) 2013 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/13810
- DOI
- 10.1016/J.COMGEO.2013.08.001
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- Computational Geometry: Theory and Applications, vol. 47, no. 1, page. 15 - 24, 2014-01
- Files in This Item:
-
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.