Complejidad de la triangulación aleatoria de Delaunay en 3D

Question

Mi pregunta:

Es el número de celdas de una triangulación tridimensional de Poisson-Delaunay con $n$ vértices $\mathcal O(n)$ con probabilidad uno?

lo que equivale a la pregunta

Es el número de vértices de Voronoi en una teselación tridimensional de Poisson-Voronoi con $n$ generadores $\mathcal O(n)$ con probabilidad uno?

Por un lado, es bien sabido que la complejidad 3d de la triangulación de Delaunay es $\mathcal O(n^2)$ en general.

Sin embargo, como se señala en [1], los únicos ejemplos conocidos que alcanzan esta complejidad proceden de distribuciones puntuales en curvas unidimensionales como la curva de momento . Además, la complejidad esperada de Poisson-Delaunay distribuida en un cubo es $\mathcal O(n)$ (por ejemplo, [2]).

Esto me lleva a la pregunta de si en realidad es casi seguro que una triangulación tridimensional de Poisson-Delauany tiene $\mathcal O(n)$ células. No he podido encontrar ninguna referencia sobre este hecho, pensamiento. Agradeceré una referencia que demuestre esta afirmación o un contraejemplo.

Editar : Para formular la cuestión de forma más matemática, en términos de configuraciones de puntos finitos, denotemos

• $Del(\gamma)$ la triangulación de Delaunay de la configuración de puntos (finitos) $\gamma$ ,
• $\mathcal S = \{\gamma \subset \mathbb R^3 : \; \#\gamma = n, Del(\gamma) \text{ has } \mathcal O(n) \text{ cells } \}$ el conjunto de todas las configuraciones de puntos con triangulaciones de Delaunay con $\mathcal O(n)$ células,
• $\Phi$ proceso puntual de Poisson homogéneo, y
• $\Phi|_B$ su restricción a un conjunto acotado de Borel $B$ . Entonces la pregunta es si $$P(\Phi|_B \in \mathcal S) = 1 $$

---

Referencias

• 1] Nina Amenta, Dominique Attali y Olivier Devillers. 2007. Complexity of Delaunay triangulation for points on lower-dimensional poliedros de baja dimensión
• 2] R. Dwyer, The expected number of k-faces of a Voronoi diagram, Computers Math. Applications 26 (5) (1993)

Answer 1

Es el número de celdas de una triangulación tridimensional de Poisson-Delaunay con $n$ vértices $\mathcal O(n)$ con probabilidad uno?

Sí. Si nuestro dominio es un dominio tridimensional.

Podemos dividir los puntos entre los puntos limítrofes, es decir, a una distancia inferior a $$n^{1\over3}\log n$$ de la frontera y puntos interiores.

Cuando $n$ va al infinito, la mayoría de los puntos son interiores.

Los puntos interiores se comportan como en un proceso de puntos de Poisson infinitos en todo el espacio $\mathbb{R}^3$ y han esperado un grado constante.

Esto es menos claro para los puntos límite sin hipótesis adicionales en el límite del dominio. Al menos podemos argumentar fácilmente a favor de una complejidad total de $$n^{4\over3},$$ que es el número de puntos límite al cuadrado, con un poco de trabajo para rebajar los factores logarítmicos.

Por un lado, es bien sabido que la complejidad 3d de la triangulación de Delaunay es $\mathcal O(n^2)$ en general.

La complejidad es $$\Omega(n^2)$$ en el peor de los casos, por ejemplo, con puntos en -o cerca de- la curva de momento o dos segmentos no coplanares.

Mi pregunta es si la propiedad se mantiene casi con seguridad, no en expectativa. ¿Su pregunta se refiere a esto? Si es así, no veo cómo.

Sin embargo, como se señala en [1], los únicos ejemplos conocidos que alcanzan esta complejidad proceden de distribuciones puntuales en curvas unidimensionales como la curva de momento .

Obsérvese que en este documento no se aborda ningún tipo de distribución probabilística. La hipótesis es que los puntos están "bien muestreados" con una idea bastante restrictiva de lo que significa. Bajo esta hipótesis el resultado no está en expectativa, no es un resultado probabilístico. Siempre se cumple.

Para formular la cuestión de forma más matemática, en términos de configuraciones de puntos finitos, denotemos

• $Del(\gamma)$ la triangulación de Delaunay de la configuración de puntos (finitos) $\gamma$ ,
• $\mathcal S = \{\gamma \subset \mathbb R^3 : \; \#\gamma = n, Del(\gamma) \text{ has } \mathcal O(n) \text{ cells } \}$ el conjunto de todas las configuraciones de puntos con triangulaciones de Delaunay con $\mathcal O(n)$ células,
• $\Phi$ proceso puntual de Poisson homogéneo, y
• $\Phi|_B$ su restricción a un conjunto acotado de Borel $B$ . Entonces la pregunta es si $$P(\Phi|_B \in \mathcal S) = 1 $$

Sigo pensando que se puede demostrar que funciona con $$\mathcal{O}(n^{4\over3})$$ en lugar de $\mathcal{O}(n)$ si $B$ es un conjunto abierto. Probablemente es difícil obtener algo mejor sin hipótesis más precisas sobre la forma de $B$ .