Brink, A. (2004) Speeding up the computation of similarity measures based on Minkowski addition in 3D. Master's Thesis / Essay, Computing Science.
|
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: | https://fse.studenttheses.ub.rug.nl/id/eprint/8941 |
Actions (login required)
 |
View Item |