Coloring by Closest Points, do they produce polygonal figures?

Question

Consider a rectangle, and $k$ points with in that rectangle. Each of the $k$ points are colored distinctly from the other $k-1$ points. Let's call this set of colored points $K$. For every other point in the rectangle, color them with the same color as the closest point (Euclidean distance) in $K$. Essentially, the rectangle is broken apart to $k$ different figures, each having a different color. Are these figures guaranteed to be polygonal? I conjecture so, but I cannot find a proof. I've written a program to generate some rectangles for me and here is one with 7 points: The cross-hairs are where each of $k$ points are.

Answer 1

The subdivision is called the Voronoi diagram of the point set, though it also has many other names.

Yes, the regions are polygonal. In fact, they are even convex polygons. The proof is simple. If the set of points is $P = \{p_1, \ldots, p_n\}$, and the "cell" containing a point $p_k \in P$ is denoted by $C(p_k)$, then we have $$ C(p_k) = \{ x : d(x,p_k) \le d(x,p_i) \text{ for } i \ne k \} = \bigcap_{i\ne k} \{ x : d(x,p_k) \le d(x,p_i)\} $$ The set $\{ x : d(x,p_k) \le d(x,p_i)\}$ is a half-space bounded by a straight line. In fact, the bounding line is the perpendicular bisector of the line from $p_k$ to $p_i$. The cell $C(p_k)$ is the intersection of a collection of these half-spaces, so it's a convex polygon.