A highly efficient algorithm for computing the vertices of the convex hull of a set of points in the plane is described and compared with existing methods. Empirical timings of a FORTRAN implementation of the algorithm show it to be faster than previous methods for most configurations of points. Careful consideration is given throughout to ensure that degenerate configurations, containing collinear or near-collinear points, are handled correctly.

A finite set of distinct points divides the plane into polygonal regions, each region containing one of the points and comprising that part of the plane nearer to its defining point than to any other. The resultant planar subdivision is called the Dirichlet tessellation; it is one of the most useful constructs associated with such a point configuration. The regions, which we call tiles, are also known as Voronoi or Thiessen polygons. We describe a recursive algorithm for computing the tessellation in a highly efficient way, and discuss the problems which arise in its implementation. Samples of graphical output demonstrate the application of the program on a modest scale; its efficiency allows its application to large sets of data, and detailed discussion of space and time considerations is given, based in part on theoretical predictions and in part on test runs on up to 10,000 points.