Samenvatting
To calculate the Minkowski-sum based similarity measure of two convex polyhedra, many relative orientations have to be considered. These relative orientations are characterized by the fact that some faces and edges of the polyhedra are parallel. For every relative orientation of the polyhedra, the volume or mixed volume of their Minkowski sum is evaluated. From the minimum of this volume, the similarity measure is calculated. In this article two issues are addressed. First, we propose and test a method to reduce the set of relative orientations to be considered by using geometric inequalities in the slope diagrams of the polyhedra. In this way, the time complexity of O(n(6)) is reduced to O(n(4.5)). Secondly, we determine which relative orientation problems are ill-posed and may be skipped because they do not maximize the similarity measure.
Originele taal-2 | English |
---|---|
Pagina's (van-tot) | 441-456 |
Aantal pagina's | 16 |
Tijdschrift | International journal of computational geometry & applications |
Volume | 19 |
Nummer van het tijdschrift | 5 |
DOI's | |
Status | Published - okt.-2009 |
Evenement | Workshop on Computational Geometry and Applications (CGA) - , Italy Duur: 14-mei-2004 → 17-mei-2004 |