Given a convex polygon, how does one test whether it's part of a Voronoi tesselation?
In other words, what is a quick way to test if a polygon is a Thiessen polygon?
I suspect one test could involve the intersection of specific perpendicular bisectors and the tessellation seeds, but not exactly sure how exactly. Any ideas?
Maybe the more general question is: can any convex polygon be a Thiessen polygon?
Any convex polygon can be realized as a Thiessen polygon. In fact, for each point in its interior, there is a corresponding realization.
For simplicity, let consider the case $\mathcal{P}$ is a convex polygon containing origin $o$ in its interior. Let $v_0,\ldots,v_{n-1}$ be the vertices of $\mathcal{P}$ in counterclockwise orientation. Let $v_n = v_0$ and for each $0 \le k < n$, let $n_k$ be the unit vector obtained by rotating $\frac{v_{k+1}-v_{k}}{|v_{k+1}-v_{k}|}$ clockwise for $90^\circ$. $n_k$ is the outward pointing normal for the sideline $v_kv_{k+1}$. $\mathcal{P}$ will be the intersection of $n$ closed half-spaces:
$$\mathcal{P} = \bigcap_{k=0}^n \mathcal{H}_k \quad\text{ where }\quad \mathcal{H}_k = \big\{ q \in \mathbb{R}^2 : q \cdot n_k \le v_k \cdot n_k \big\} $$
Let $r_k = 2(n_k\cdot v_k)n_k$ be the image of $o$ under reflection with respect to sideline $v_k v_{k+1}$. For any point $q \in \mathbb{R}^2$, the condition that $q$ is at least as close to $o$ than $r_k$ is
$$|q - r_k|^2 - |q|^2 \ge 0 \iff r_k^2 - 2 r_k \cdot q \ge 0 \iff (n_k\cdot v_k)(n_k\cdot v_k - n_k \cdot q) \ge 0$$
Since $o$ lies in the interior of $\mathcal{P}$, all those $n_k \cdot v_k$ appear in the definition of $\mathcal{H}_k$ are positive. Above condition is equivalent to
$$n_k\cdot v_k - n_k \cdot q \ge 0\iff q \in \mathcal{H}_k$$
Combine conditions for all $k$, we find $q$ lies in the Thiessen polygon associated with $o, r_0,\ldots, r_{n-1}$ when and only when $q \in \mathcal{P}$. i.e. $\mathcal{P}$ can be realized as the Thiessen polygon for $o$ and its mirror images.