GVDs

Generalized Voronoi diagrams (GVDs) are a family of spatial partitions that extend the classical Voronoi diagram by using generalized distance functions to a set of sites. In a GVD, each point in space is assigned to the site for which the distance, as defined by the chosen metric, is minimal. Unlike standard Voronoi diagrams that rely on Euclidean distance, GVDs can incorporate weights, anisotropy, or non-Euclidean geometries, producing cells that may be non-convex, irregular, or even disconnected.

Common variants include additively weighted Voronoi diagrams (Johnson-Mehl), where each site has a weight added to its distance; multiplicatively weighted diagrams (Apollonius diagrams) with site-specific multiplicative factors; and power diagrams, which arise from a quadratic distance function and can represent a broad family of site influences. Geodesic Voronoi diagrams compute distances along a surface, while other GVDs use metrics such as L1 or Linf or distance functions that vary spatially. Because of these generalizations, GVDs can capture a wider range of proximity relations than ordinary Voronoi diagrams.

Construction and computation of GVDs depend on the chosen metric. Some variants admit efficient algorithms (e.g., certain power diagrams via lifting transforms), while others rely on shortest-path methods on surfaces or discrete approximations. In practice, multiple variants may be implemented within computational geometry libraries.

Applications span robotics and motion planning, geographic information systems, wireless network modeling, computer graphics, clustering, and spatial analysis. Limitations include increased computational complexity, potential non-convexity of cells, and numerical sensitivity to weights or degeneracies. Note that the acronym GVD can also refer to different concepts in other fields, so context matters.