Geometry Tools

psdr.voronoi_vertex(domain, Xhat, X0, L=None, randomize=True)[source]

Constructs a subset of the Voronoi vertices on a given domain

Given a domain \(\mathcal{D} \subset \mathbb{R}^m\), a set of points \(\lbrace \widehat{\mathbf{x}}_j \rbrace_{j=1}^M\), and a distance metric

\[d(\mathbf{x}_1, \mathbf{x}_2) = \|\mathbf{L}(\mathbf{x}_1 - \mathbf{x}_2)\|_2\]

the vertices of the bounded Voronoi diagram \(\mathbf{v}_i \in \mathcal{D}\) are those points are those points that satisfy \(r\) equidistance constraints in the metric \(d\)

\[\| \mathbf{L}(\mathbf{v}_i - \widehat{\mathbf{x}}_{\mathcal{I}_i[1]})\|_2 = \| \mathbf{L}(\mathbf{v}_i - \widehat{\mathbf{x}}_{\mathcal{I}_i[2]})\|_2 = \ldots = \| \mathbf{L}(\mathbf{v}_i - \widehat{\mathbf{x}}_{\mathcal{I}_i[r]})\|_2\]

and \(m-r\) constraints from the domain.

The bounded Voronoi vertices include the vertices of the domain. The number of domain vertices can grow exponentially in dimension (e.g., consider the cube), but the asymptotic cost of finding these is \(\mathcal{O}(mn)\) [wikiVEP] per vertex where \(n\) is the number of linear inequality constraints specifying the domain. Hence, the complexity of finding the Voronoi vertices grows exponentially in the dimension of the domain. Thus we use an approach due Lindemann and Cheng [LC05] to find a subset of vertices by taking a starting point \(\mathbf{x}_0\) and sequentially projecting it onto a series of hyperplanes such that after \(m\) steps we satisfy \(m\) constraints.

Parameters:
  • domain (Domain) – Domain on which to construct the vertices
  • Xhat (array-like (M, m)) – M existing points on the domain which define the Voronoi diagram
  • X0 (array-like (N, m)) – Initial points to use to find vertices
  • L (array-like (m, m), optional) – Weight on distance in 2-norm; defaults to the identity matrix
  • randomize (bool, optional (default: True)) – If true, when L is rank deficient add a random direction at each step such that we find points on the boundary of the domain satisfying m constraints.
Returns:

X – Points satisfying m constraints

Return type:

np.ndarray(N, m)

References

[LC05]Iteratively Locating Voronoi Vertices for Dispersion Estimation Stephen R. Lindemann and Peng Cheng Proceedings of the 2005 Interational Conference on Robotics and Automation
[wikiVEP]Vertex enumeration problem, Wikipedia. https://en.wikipedia.org/wiki/Vertex_enumeration_problem