Reducing the Time Complexity and Identifying Ill-Posed Problem Instances of Minkowski Sum Based Similarity Calculations

H. Bekker*, A.A. Brink, J.B.T.M. Roerdink

*Corresponding author voor dit werk

OnderzoeksoutputAcademicpeer review

1 Citaat (Scopus)

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-2English
Pagina's (van-tot)441-456
Aantal pagina's16
TijdschriftInternational journal of computational geometry & applications
Volume19
Nummer van het tijdschrift5
DOI's
StatusPublished - okt.-2009
EvenementWorkshop on Computational Geometry and Applications (CGA) - , Italy
Duur: 14-mei-200417-mei-2004

Vingerafdruk

Duik in de onderzoeksthema's van 'Reducing the Time Complexity and Identifying Ill-Posed Problem Instances of Minkowski Sum Based Similarity Calculations'. Samen vormen ze een unieke vingerafdruk.

Citeer dit