Definition:
Assume that a set of points $P=\{p_1,\dots,p_n\}$ on a line is given. The Voronoi diagram of $P$ is a set of points $V(P)=\{x_1,\dots,x_{n-1}\}$ such that $x_i$ is the midpoint of $p_i p_{i+1}$.
Question:
- Suppose you are given a set $X=\{x_1,\dots,x_{n-1}\}$. How can we determine whether or not $X$ is a one-dimensional Voronoi diagram of a set of points?
- If $X$ is indeed a one-dimensional Voronoi diagram, How can we determine $P$?
My try:
I believe that it suffices for the points of $X$ to be on the same line in order to be a one-dimensional Voronoi diagram. Also, for the second part, I have an idea. We know that:
$$x_1 = \frac{p_1+p_2}{2} \implies p_2=2x_1-p_1$$
$$x_2 = \frac{p_2+p_3}{2} \implies p_3=2x_2-(2x_1-p_1)$$
$$\dots$$
$$x_{n-1} = \frac{p_{n-1}+p_n}{2} \implies p_n=2x_{n-1}-p_{n-1}$$
So if we determine $p_1$, we get every other point of $P$ according to these equations. But I'm stuck at determining $p_1$.
Best Answer
For (2), knowing $V(P)$ is not sufficient to determine $P$. For example, if $V(P) = \{5,15\}$ then $P$ could be $\{0,10,20\}$ or $\{1,9,21\}$ or $\{2,8,22\}$ etc.
Difficulty is that $V(P)$ gives you $n-1$ linear equations in $n$ unknowns, so system is underdetermined. Additional constraint that $p_{k+1} \ge p_k$ is not sufficient to give a unique solution.