Computing Dirichlet Tessellations in the Plane

TLDR

A finite set of distinct points partitions the plane into polygonal regions, each containing one point and consisting of points closer to that point than any other, forming the Dirichlet tessellation, also known as Voronoi or Thiessen polygons, a widely used construct. The study aims to present a recursive algorithm for efficiently computing the Dirichlet tessellation. The algorithm’s implementation challenges are analyzed, highlighting issues that arise during execution. Graphical examples and performance tests on up to 10,000 points show the program’s efficiency and scalability, with space and time analyses supported by theory and empirical results.

Abstract

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.