Elección de los pesos de un diagrama de Voronoi -- ¿es esta función siempre el gradiente de otra función?

Question

Esta pregunta está relacionada con la anterior Área ponderada de una célula de Voronoi . Como en esa pregunta, dejemos que $X = \{ x_1,\dots,x_n\} $ denotan un conjunto de $n$ puntos del cuadrado unitario $S = [0,1]\times[0,1]$ y que $w = \{w_1,\dots,w_n\}$ denotan un conjunto de pesos correspondientes al $n$ puntos en $X$ . Definir el "diagrama de potencia" de $X$ en $S$ sea una partición de $S$ en un máximo de $n$ piezas $V_i(\mathbf{w})$ donde

$V_i(\mathbf{w}) = \{x\in S: \|x - x_i\|^2 + w_i \leq \|x - x_j\|^2 + w_j \forall j \neq i \}$

es decir, un "diagrama de Voronoi ponderado". Así, los valores mayores de $w_i$ corresponden a celdas más pequeñas $V_i$ . Las celdas son siempre convexas, y la partición no cambia si añadimos una constante a todos los términos de un vector de pesos $\mathbf{w}$ .

Mi pregunta es: consideremos alguna cantidad $Q(V_i(\mathbf{w}))$ asociado a las células de Voronoi con la siguiente propiedad de monotonicidad: para cualesquiera dos vectores de peso $\mathbf{w}$ y $\mathbf{w}'$ si resulta que $V_i(\mathbf{w})\subsetneq V_i(\mathbf{w}')$ entonces $Q(V_i(\mathbf{w})) < Q(V_i(\mathbf{w}'))$ . Ejemplos de $Q$ sería el área, el perímetro, el diámetro o la anchura de las celdas. Quiero saber: ¿es siempre el caso que $Q(V_i(\mathbf{w}))$ ¿es de alguna manera "equivalente" al gradiente de alguna otra función?

Mi razonamiento para esta pregunta es el siguiente: supongamos que queremos seleccionar pesos $\mathbf{w}$ tal que $Q(V_i(\mathbf{w}))$ es igual para todos $i$ . Esto significa que queremos aumentar (resp. disminuir) los valores de $w_i$ para las regiones en las que $Q(V_i(\mathbf{w}))$ es grande (o pequeño). Una forma sensata de hacerlo sería establecer iterativamente $w_i \mapsto w_i + \epsilon Q(V_i(\mathbf{w})) $ donde $\epsilon$ es algún pequeño paso. He intentado experimentos numéricos con este esquema para el caso en que $Q$ mide el área o el perímetro y esto parece funcionar.

Answer 1

Si nos fijamos en el último párrafo de su pregunta, podría parecer razonable reformular la pregunta como: ¿podemos seleccionar siempre pesos $\mathbf{w}$ tal que los valores $Q(V_i(\mathbf{w}))$ satisfacen relaciones prescritas: si normalizamos por la suma de todas las entradas $$s(\mathbf{w}):=\sum_{i=1}^nQ(V_i(\mathbf{w}))$$ obtenemos un vector $$Q_{\text{norm}}(\mathbf{w}):=\frac{1}{s(\mathbf{w})}(Q(V_i(\mathbf{w})))_{1\leq i\leq n}$$ que está contenido en el simplex $\Delta_{n-1}=\{(x_i)_{1\leq i\leq n}|\sum_i=1\}$ . Entonces la pregunta es: ¿podemos encontrar para cada punto $p\in\Delta_{n-1}$ pesos $\mathbf{w}$ tal que $Q_{\text{norm}}=p$ . Por ejemplo, si tomamos $p$ para ser el baricentro de $\Delta_{n-1}$ entonces querríamos seleccionar pesos tales que $Q(V_i(\mathbf{w}))$ son iguales para todos $i$ .

Puedo responder a esta pregunta completamente bajo el supuesto adicional de que $Q$ es continua. (Tus ejemplos "área, perímetro, diámetro o anchura de las celdas" son todos continuos). Lo que tenemos que demostrar es la subjetividad del mapa continuo $$Q_{\text{norm}}\colon\, \mathbb{R}^n\to \Delta_{n-1}.$$ Consideramos un mapa $$\begin{align}f\colon\, \Delta_{n-1}&\to\mathbb{R}^n\\x=(x_1,\dots,x_n)&\mapsto f(x)=(\log(x_1),\dots,\log(x_n)).\end{align}$$ Sólo se define en el interior de $\Delta_{n-1}$ pero ampliamos la definición en el límite $\partial\Delta_{n-1}$ estableciendo $\log(0)=-\infty$ . También ampliamos la definición del diagrama de Voronoi para permitir que algunos (pero no todos) los componentes del vector peso sean $-\infty$ las regiones de Voronoi correspondientes estarán vacías. Estas definiciones nos permiten componer $f$ con $Q_{\text{norm}}$ para obtener el mapa $$Q_{\text{norm}}\circ f\colon\, \Delta_{n-1}\to\Delta_{n-1},$$ que es continuo y tiene las bonitas propiedades de asignar caras a caras: Si algunas coordenadas de $x$ son cero, las coordenadas correspondientes en $f(x)$ son $-\infty$ y las coordenadas correspondientes en $Q_{\text{norm}}\circ f(x)$ también son cero, ya que las regiones de Voronoi correspondientes están vacías. Por lo tanto, una cara de $\Delta_{n−1}$ se asigna a sí mismo.

Entonces podemos aplicar un pequeño (pero a menudo útil) lema de topología algebraica que afirma que dicho mapa debe ser suryectivo. Ver para esta pregunta (y las respuestas): Mapa del símplex a sí mismo que conserva los subsímplex . Por lo tanto $Q_{\text{norm}}\circ f$ es suryectiva y, por tanto, también $Q_{\text{norm}}$ es suryectiva, que es lo que queríamos demostrar.

Editar : Si $Q$ se toma como área y se busca una partición con todas las áreas iguales, entonces esta partición es par único hasta conjuntos de medida cero. Una buena prueba de esta demostración geométrica se da en el siguiente documento, donde también consideran algunas generalizaciones de la cuestión:

Darius Geiß, Rolf Klein, Rainer Penninger y Günter Rote, Resolución óptima de un problema de transporte mediante diagramas de Voronoi , Geometría Computacional, Teoría y Aplicaciones 46 (2013), 1009-1016, número especial para el 28th European Workshop on Computational Geometry (EuroCG'12).

(No es el primero prueba de estos resultados, véanse las referencias de este documento).