Minimum perimeter convex hull of imprecise points

Linqiao and I have made a mini movie on the subject of computing minimum perimeter convex hulls of imprecise points. The movie has been accepted for the multimedia session of SoCG 2011.

Here is the Computational Geometry web site, where various conferences on Computational Geometry can be found.

Given a set of imprecise points on a plane, each is constrained within a convex region of the plane, the problem is to find the set of positions such that the perimeter of their convex hull will be as small as possible.

This movie explains a few theoretical findings, and demonstrates an algorithm based on a physical interpretation.

The movie is available through YouTube:

Here is an extended abstract accompanying the movie.