Convex Optimization · Problem 2.7

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · voronoi-halfspace

Problem

Voronoi description of halfspace. Let aa and bb be distinct points in Rn\mathbf{R}^n. Show that the set of all points that are closer (in Euclidean norm) to aa than bb, i.e., {x∣∥x−a∥2≤∥x−b∥2}\{x \mid \|x - a\|_2 \leq \|x - b\|_2\}, is a halfspace. Describe it explicitly as an inequality of the form cTx≤dc^T x \leq d. Draw a picture.

Browse the problem library