University of British Columbia
A convex hull algorithm optimal for point sets in even dimensions
Abstract
dc:descriptionFinding the convex hull of a finite set of points is important not only for practical applications but also for theoretical reasons: a number of geometrical problems, such as constructing Voronoi diagrams or intersecting hyperspheres, can be reduced to the convex hull problem, and a fast convex hull algorithm yields fast algorithms for these other problems. This thesis deals with the problem of constructing the convex hull of a finite point set in R . Mathematical properties of convex hulls are developed, in particular, their facial structure, their representation, bounds on the number of faces, and the concept of duality. The main result of this thesis is an O(nlogn + n[(d+1)/2]) algorithm for the construction of the convex hull of n points in Rd. It is shown that this algorithm is worst case optimal for even d≥2.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 1981
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Seidel, Raimund
Rights
dc:rights- Statement dc:rights
-
- For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/22652