# 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:

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

• Regarding question 1, I don’t think every set of points on a line can be a Voronoi diagram. For example consider two points ‘close’ to each other, then a large gap to another two points that are ‘close’ to each other. There must exist some relationship between the sequential gaps I’m guessing.. – T. Fo Dec 12 '18 at 8:27
• For the general problem, see the paper Recognizing Dirichlet tessellations. – lhf Dec 12 '18 at 10:23

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.

• Can you provide an example? – Arman Malekzadeh Dec 12 '18 at 9:30
• I'll compute the actual inequalities as soon as I have some time. – RcnSc Dec 12 '18 at 9:42
• @ArmanMalekzadeh Let me know if something is unclear – RcnSc Dec 12 '18 at 10:14
• Thank you... I was just wondering if the solution was unique. It seems it's not :) – Arman Malekzadeh Dec 12 '18 at 10:28

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.