Convex Hull Computations

Authored by: Raimund Seidel

Discrete and Computational Geometry

Print publication date:  April  2004
Online publication date:  April  2004

Print ISBN: 9781584883012
eBook ISBN: 9781420035315
Adobe ISBN:


 Download Chapter



The “convex hull problem” is a catch-all phrase for computing various descriptions of a polytope that is either specified as the convex hull of a finite point set in ? d or as the intersection of a finite number of halfspaces. We first define the various problems and discuss their mutual relationships (Section 22.1). We discuss the very special case of the irredundancy problem in Section 22.2. We consider general dimension d in Section 22.3 and describe the most common general algorithmic approaches along with the best run-time bounds achieved so far. In Section 22.4 we consider separately the case of small dimensions d = 2, 3, 4, 5. Finally, Section 22.5 addresses various issues related to the convex hull problem.

Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.