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}
 Voronoi diagrams in higherdimensional spaces.
 Voronoi diagrams in spaces endowed with different metrics and distance functions.
 Voronoi diagrams of not just points but various types of geometric objects.
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 socalled 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, straightline segments and circular arcs. In Held and Huber [HeHu08, HeHu09], we generalized the topologyoriented approach of Sugihara and Iri^{3} in order to compute the Voronoi diagram of points, straightline 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, straightline segments and circular arcs on an industrialstrength 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 Minkowskisums.
For more details on VRONI, ArcVRONI, industrial and scientific applications of Voronoi diagrams, and example figures I refer to Martin Held’s website.
Variableradius 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 wavefront^{4}. 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 nonuniform speeds and, in return, get as the dual skeleton structure a generalized Voronoi diagram, which we call variableradius Voronoi diagram.

P. M. Gruber, Convex and discrete geometry, SpringerVerlag New York, 2007. ↩

F. Aurenhammer, Voronoi diagrams  a survey of a fundamental geometric data structure, ACM Computing Surveys, pp. 345405, vol. 23(3), 1991. ↩

K. Sugihara and M. Iri, Construction of the Voronoi diagram for ‘one million’ generators in singleprecision arithmetic, pp. 14711484, vol 80(9), Proceedings of the IEEE, 1992. ↩

The wavefront propagation is sometimes called grassfire model. ↩