Meeting 10: 3-D Convex Hulls; k-D Convex Polytopes

Exercise 2 is due today !

Introductory remarks:

Most applications of convex hulls in graphics are in two or three
dimensions, as these are the most natural mapping for most
problems, and 2-D and 3-D are more amenable to visualization
than are higher dimensions.

We treated 2-D convex hulls, their definition, construction, and
use, in Meeting 5.  Today we consider 3-D convex hulls, and
(briefly) the general-dimensional case.  Three dimensions turn
out to be "special" in that algorithms for 3-D hull construction,
and bounds on the resulting complexity, are different from what
one might expect if one considered very high-dimensions first,
then worked downward.

Presenters:

Brendon Glazer
Edwin Foo

Readings:

• O'Rourke Chapter 4
• de Berg Chapter 11
• Preparata & Shamos Chapter 3

• GeomView
• QHull

Next time we will go back to 2-D, and see some real applications
of 2-D linespace.  This will lay the groundwork for our treatment
of 3-D linespace later in the semester.
 

Next Meeting

Last Meeting .... Next Meeting .... Course Page .... Meeting Schedule

Created: Feb 1998