Convex Optimization · Problem 2.9

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · voronoi-sets-polyhedral-decomposition

Problem

Voronoi sets and polyhedral decomposition. Let x0,…,xK∈Rnx_0, \ldots, x_K \in \mathbf{R}^n be distinct. Consider the set of points that are closer (in Euclidean norm) to x0x_0 than the other xix_i, i.e., V={x∈Rn∣∥x−x0∥2≤∥x−xi∥2, i=1,…,K}.V = \{x \in \mathbf{R}^n \mid \|x - x_0\|_2 \leq \|x - x_i\|_2,\, i = 1, \ldots, K\}. VV is called the Voronoi region around x0x_0 with respect to x1,…,xKx_1, \ldots, x_K. ((a)) Show that VV is a polyhedron. Express VV in the form V={x∣Ax⪯b}V = \{x \mid Ax \preceq b\}. ((b)) Conversely, given a polyhedron PP with nonempty interior, show how to find x0,…,xKx_0, \ldots, x_K so that the polyhedron is the Voronoi region of x0x_0 with respect to x1,…,xKx_1, \ldots, x_K. ((c)) We can also consider the sets Vk={x∈Rn∣∥x−xk∥2≤∥x−xi∥2, i≠k}.V_k = \{x \in \mathbf{R}^n \mid \|x - x_k\|_2 \leq \|x - x_i\|_2,\, i \neq k\}. The set VkV_k consists of points in Rn\mathbf{R}^n for which the closest point in the set {x0,…,xK}\{x_0, \ldots, x_K\} is xkx_k. The sets V0,…,VKV_0, \ldots, V_K give a polyhedral decomposition of Rn\mathbf{R}^n. More precisely, the sets VkV_k are polyhedra with nonempty interior, ⋃k=0KVk=Rn\bigcup_{k=0}^K V_k = \mathbf{R}^n, and int Vi∩int Vj=∅\mathbf{int}\, V_i \cap \mathbf{int}\, V_j = \emptyset for i≠ji \neq j, i.e., ViV_i and VjV_j intersect at most along a boundary. Suppose that P1,…,PmP_1, \ldots, P_m are polyhedra with nonempty interior such that ⋃i=1mPi=Rn\bigcup_{i=1}^m P_i = \mathbf{R}^n, int Pi∩int Pj=∅\mathbf{int}\, P_i \cap \mathbf{int}\, P_j = \emptyset for i≠ji \neq j. Can this polyhedral decomposition of Rn\mathbf{R}^n be described as the Voronoi regions generated by an appropriate set of points?

Browse the problem library