Javascript must be enabled for the correct page display

Speeding up the computation of similarity measures based on Minkowski addition in 3D

Brink, A. (2004) Speeding up the computation of similarity measures based on Minkowski addition in 3D. Master's Thesis / Essay, Computing Science.

[img]
Preview
Text
Infor_Ma_2004_ABrink.CV.pdf - Published Version

Download (1MB) | Preview

Abstract

The shape of two objects can be compared by a computer program using similarity measures. The family of similarity measures based on Minkowski addition provides a well-founded way to do this. In practice, they are restricted to comparing the shapes of convex polyhedra. We describe two variants of these measures. The first variant uses the volume of the Minkowski sum, and the second variant uses the so-called mixed volume of the Minkowski sum. Current implementations have the disadvantage that they are very timeconsuming: their time complexity is proportional to n6, where n is proportional to the complexity of the polyhedra. We developed, implemented and tested improved algorithms for both variants. These algorithms proved to reduce the time complexity to n45.

Item Type: Thesis (Master's Thesis / Essay)
Degree programme: Computing Science
Thesis type: Master's Thesis / Essay
Language: English
Date Deposited: 15 Feb 2018 07:30
Last Modified: 15 Feb 2018 07:30
URI: http://fse.studenttheses.ub.rug.nl/id/eprint/8941

Actions (login required)

View Item View Item