Convex Hull
  Instructions
  Details
  Demo
  Try It!

Introduction

The problem is to find the convex hull of the points or the polygon. That is, a polygonal area that is of smallest length and so that any pair of points within the area have the line segment between them contained entirely inside the area.

The problem is, given a collection of points or a polygonal area, to find the convex hull of the points or of the polygon.

A solution to this problem is useful, for instance, in the case of enclosing a given collection of points, or objects, on a plane, using a fence of shortest total length. The area inside the fence of shortest length will be convex: the line interval connecting any two points inside, will lie entirely inside the area.

This project is made possible by Professor Dorit S. Hochbaum's ONR research grant N00014-91-J-1241.

Questions or comments? Send mail to Professor Hochbaum.