Maximum overlap and minimum convex hull of two convex polyhedra under translations
SCIE
SCOPUS
- Title
- Maximum overlap and minimum convex hull of two convex polyhedra under translations
- Authors
- Ahn, HK; Brass, P; Shin, CS
- Date Issued
- 2008-07
- Publisher
- Elsevier BV
- Abstract
- Given two convex polyhedra P and Q in three-dimensional space, we consider two related problems of shape matching: (1) finding a translation t(1) is an element of R-3 of Q that maximizes the volume of their overlap P boolean AND (Q + t(1)), and (2) finding a translation t(2) is an element of R-3 that minimizes the volume of the convex hull of P boolean OR (Q + t(2)). For the maximum overlap problem, we observe that the dth root of the objective function is concave and present an algorithm that computes the optimal translation in expected time O(n(3) logo n). This method generalizes to higher dimensions d > 3 with expected running time O(n(d+1-3/d) (log n)(d+1)). For the minimum convex hull problem, we show that the objective function is convex. The same method used for the maximum overlap problem can be applied to this problem and the optimal translation can be computed in the same time bound. (C) 2007 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/29422
- DOI
- 10.1016/j.comgeo.2007.08.001
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- Computational Geometry: Theory and Applications, vol. 40, no. 2, page. 171 - 177, 2008-07
- 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.