De Raedt, K. (2002) Calculating the Overlay of Connected Subdivisions On a Sphere Using a Planar Overlay Algorithm. Master's Thesis / Essay, Computing Science.
|
Text
Infor_Ma_2002_KDeRaedt.CV.pdf - Published Version Download (864kB) | Preview |
Abstract
One approach to determine the similarity between two convex 3D polyhedrais to calculate the Minkowski sum of the polyhedra. The Minkowski sum of two convex 3D polyhedra can be computed efficiently by an attributed graph overlay of their slope diagrams. In this paper we describe a method to calculate the graph overlay of the slope diagrams on the sphere using a planar overlay algorithm, via a mapping to a tetrahedron. Our planar overlay algorithm can be adapted to work directly on the sphere. However due to the complexity of the line intersection on the sphere the running time increases by a factor of three. We study the algorithmic complexity of the graph overlay algorithm and the mapping from the sphere to the plane theoretically and by numerical experiment.
| 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/8884 |
Actions (login required)
 |
View Item |