Generalized Voronoi diagrams

Introduction. Voronoi diagrams of points in the Euclidean plane were first defined one and a half centuries ago by Lejeune Dirichlet when investigating quadratic forms.1 Besides the basic Voronoi diagrams of points, various generalizations have been of interest in the field computational geometry:2

All these kinds of Voronoi diagrams have in common that we consider a finite set of input objects. Then the Voronoi diagram of these objects tessellates the space into so-called Voronoi cells such that (i) every Voronoi cell uniquely belongs to an object and (ii) the Voronoi cell of an object A comprises those points that are closer to A than to any other object B.

Voronoi diagram of points, straight-line segments and circular arcs

Voronoi diagram of points, straight-line segments and circular arcs. In Held and Huber [HeHu08, HeHu09], we generalized the topology-oriented approach of Sugihara and Iri3 in order to compute the Voronoi diagram of points, straight-line segments and circular arcs. The resulting implementation ArcVRONI is an extension to Held’s VRONI, which adds circular arcs to the list of supported input primitiva.

To our knowledge, ArcVRONI is still the only available Voronoi code that is able to compute the Voronoi diagram of points, straight-line segments and circular arcs on an industrial-strength level. ArcVRONI is available for commercial and academical use and, in fact, has been licensed for many industrial applications. Besides Voronoi diagrams, ArcVRONI also features the computation of the medial axis and offset curves based on Minkowski-sums.

For more details on VRONI, ArcVRONI, industrial and scientific applications of Voronoi diagrams, and example figures I refer to Martin Held’s website.

Voronoi diagram and offset curves

Variable-radius Voronoi diagram. In [HHP16, HHP15b,HHP15], we further generalized Voronoi diagrams in the following way: Similar to straight skeletons, one can define Voronoi diagrams as the interference pattern of a propagating wavefront4. The wavefront is an offset curve that is based on Minkowski sums with disks of a fixed radius. In this sense, the wavefront grows everywhere at unit speed. We generalized the wavefront process to non-uniform speeds and, in return, get as the dual skeleton structure a generalized Voronoi diagram, which we call variable-radius Voronoi diagram.

Variable-radius Voronoi diagram

  1. P. M. Gruber, Convex and discrete geometry, Springer-Verlag New York, 2007. 

  2. F. Aurenhammer, Voronoi diagrams - a survey of a fundamental geometric data structure, ACM Computing Surveys, pp. 345-405, vol. 23(3), 1991. 

  3. K. Sugihara and M. Iri, Construction of the Voronoi diagram for ‘one million’ generators in single-precision arithmetic, pp. 1471-1484, vol 80(9), Proceedings of the IEEE, 1992. 

  4. The wavefront propagation is sometimes called grassfire model.