Meeting 5: 2D Convex Hulls

Introductory remarks

So far we have discussed representation of fundamental geometric primitives, such as
points and oriented halfspaces, both in ordinary cartesian coordinates, and in (oriented)
homogenous coordinates.  Along with primitive representations, we discussed several
fundamental operators on these representations:  inner product, cross product, leftof(),
etc.

We also introduced the notion of duality, in which statements in some space have analogues
in a dual space.   Finally, we discussed adjacency data structures which encode proximity
and/or neighbor relations among parts of a geometric object, for example among vertices
and edges of a 2D polygon, or among vertices, edges, and faces of a 3D polyhedron.

Today, we consider our first example of an algorithmically generated geometric object,
the convex hull of a point set, or of a set of halfspaces, in two dimensions.   Convex hulls
are a good initial example to tie together all of the above issues:  representation, operators,
adjacency data structures, and duality.  Indeed, we will show an example in which duality
is applied operationally, to transform one kind of convex hull statement (which, at first
glance, seems difficult to solve) into another problem whose solution is straightforward.

Convex hulls are fundamental objects in computational geometry and graphics.  In
graphics, convex hulls are used, for example, when generating hierarchical object
bounds for object culling, collision detection, etc., and conservative visibility
computations, and for a myriad of other uses.

Presenters:

Haiyang Liu
Wei Cai

Readings:

• de Berg et al., Chapter 1
• O'Rourke Chapter 3

• 1
• 2

• Definition of convexity; examples (picture!)
• State convex hull problem for n vertices v_i
• Identify set of vertices {v_i} on convex hull
• Identify set of edges {v_iv_j} on convex hull
• Identify vertices/edges in order around hull
• What is true about every convex hull edge ?
• Picture!
• Give a naive O(n^3) algorithm (every edge, every vertex)
• Picture!
• What is time complexity?
• Show giftwrapping algorithm
• Show operation!
• Distinguish complexity as function of input size, output size

• in 1:
• Output-sensitive algorithm
• Degeneracies and robustness
• Duality, to compute convex hull of halfspaces

• Online version of convex hull
• Optimizations (e.g., quickhull)

Next Meeting

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

Created: Feb 1998