Xrfgtjtk

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$.

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.

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.