5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – T. Fo Dec 12 '18 at 8:27
  • $\begingroup$ For the general problem, see the paper Recognizing Dirichlet tessellations. $\endgroup$ – lhf Dec 12 '18 at 10:23
1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.