Given the Voronoi diagram of some points on a line, determine the points

Question

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:

1. 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?
2. 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$.

Answer 1

Every point $x_i$ is equidistant of two points $p_i$ and $p_{i+1}$. Let's call that distance $d_i$. We also know that $p_{i+1} - p_i = (p_{i+1} - x_{i+1}) + (x_{i+1} - p_i) = d_{i+1} + d_i$. The $d_i$ are distances so they're all positive.

For a given set $X$ with $n$ elements, you have $n-1$ linear equations and $n$ inequalities (all the distances must be positive). One way to solve it is to compute your vector $(d_1,...d_n)$ as a function of $d_1$ and check whether there's a $d_1$ for which all the $d_i$ are positive.

All the $d_i$ are linear in $d_1$, so your inequalities will translate to linear inequalities on $d_1$ of the form $(-1)^{b_i}d_1 \le c_i$, which may or may not have a solution depending on the specific values.

Edit: Computing the actual inequalities.

We're trying to express all the $d_i$ as a function of $d_1$.

$$d_2 + d_1 = (p_2 - p_1) \Leftrightarrow d_2 = (p_2 - p_1) - d_1$$ $$d_3 + d_2 = (p_3 - p_2) \Leftrightarrow d_3 = (p_3 - p_2) - d_2 = (p_3 - p_2) - (p_2 - p_1) + d_1$$ $$...$$ $$d_i = \sum_{j = 0}^{i-1} (-1)^j(p_{i-j} - p_{i-j-1}) + (-1)^{i-1} d_1$$

So: $$d_i \ge 0 \Leftrightarrow (-1)^{i-1} d_1 \ge -\sum_{j = 0}^{i-1} (-1)^j(p_{i-j} - p_{i-j-1}) $$

Your set is a Voronoi diagram if and only if there's a $d_1$ that satisfies all these inequalities.

Answer 2

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.