Dado el diagrama de Voronoi de algunos puntos en una línea, determinar los puntos

Question

Definición:

Supongamos que un conjunto de puntos de $P=\{p_1,\dots,p_n\}$ en una línea dada. El diagrama de Voronoi de $P$ es un conjunto de puntos de $V(P)=\{x_1,\dots,x_{n-1}\}$ tal que $x_i$ es el punto medio de la $p_i p_{i+1}$.

Pregunta:

1. Suponga que se dan una serie $X=\{x_1,\dots,x_{n-1}\}$. ¿Cómo podemos determinar si o no $X$ es unidimensional diagrama de Voronoi de un conjunto de puntos?
2. Si $X$ es de hecho un one-dimensional diagrama de Voronoi, ¿Cómo podemos determinar el $P$?

Yo:

Yo creo que es suficiente para que los puntos de $X$ a estar en la misma línea con el fin de ser unidimensional diagrama de Voronoi. También, para la segunda parte, tengo una idea. Sabemos que:

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

Así que si determinamos $p_1$, obtenemos cada otro punto de $P$ según estas ecuaciones. Pero estoy atascado en la determinación de $p_1$.

Answer 1

Para (2), a sabiendas de $V(P)$ no es suficiente para determinar $P$. Por ejemplo, si $V(P) = \{5,15\}$ entonces $P$ podría ser $\{0,10,20\}$ o $\{1,9,21\}$ o $\{2,8,22\}$ etc.

La dificultad es que $V(P)$ da $n-1$ ecuaciones lineales en $n$ incógnitas, por lo tanto el sistema es indeterminado. Restricción adicional de que el $p_{k+1} \ge p_k$ no es suficiente para dar una solución única.

Answer 2

Cada punto de $x_i$ es equidistante de los dos puntos de $p_i$ e $p_{i+1}$. Vamos a llamar a esa distancia $d_i$. También sabemos que $p_{i+1} - p_i = (p_{i+1} - x_{i+1}) + (x_{i+1} - p_i) = d_{i+1} + d_i$. El $d_i$ son distancias así son todos positivos.

Para un conjunto dado $X$ con $n$ elementos, ha $n-1$ ecuaciones lineales y $n$ desigualdades (todas las distancias deben ser positivo). Una forma de resolverlo es calcular el vector $(d_1,...d_n)$ como una función de la $d_1$ y compruebe si hay un $d_1$ para que todos los $d_i$ son positivos.

Todas las $d_i$ son lineales en $d_1$, por lo que su desigualdades se traducen a desigualdades lineales en $d_1$ de la forma $(-1)^{b_i}d_1 \le c_i$, que puede o no puede tener una solución que depende de los valores específicos.

Edit: la Informática de la real de las desigualdades.

Estamos tratando de expresar todas las $d_i$ como una función de la $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$$

Así: $$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}) $$

Su conjunto es un diagrama de Voronoi si y sólo si hay un $d_1$ que cumple con todas estas desigualdades.