Return to search

A convex hull algorithm optimal for point sets in even dimensions

Finding 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. / Science, Faculty of / Computer Science, Department of / Graduate
Date January 1981
CreatorsSeidel, Raimund
Source SetsUniversity of British Columbia
Detected LanguageEnglish
TypeText, Thesis/Dissertation
RightsFor non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use

Page generated in 0.0029 seconds