# The ICICS/CS Reading Room

## UBC CS TR-81-14 Summary

- No on-line copy of this technical report is available.

- A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, September 1981 Raimund Seidel
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.
.br
This thesis deals with the problem of constructing the
convex hull of a finite point set in $R^{d}$. 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(n \log n + n^{\lfloor(d+1)/2\rfloor})$ algorithm for the
construction of the convex hull of $n$ points in $R^{d}$. It is shown
that this algorithm is worst case optimal for even $d \geq 2$.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.