Given the Voronoi diagram of some points on a line, determine the points 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$.
 A: 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.
A: 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.
