Grado medio de vértices convexa en una triangulación de Delaunay

Question

Deje $P \subset \mathbb{R}^2$. El límite de $DT(P)$, la triangulación de Delaunay de la de punto de ajuste $P$$conv(P)$. También se sabe que el promedio de grado de los vértices de $DT(P)$$\lt 6$. Mi pregunta es hay límite en el nivel esperado del casco vértices de $DT(P)$? Hay un argumento intuitivo al menos para esta obligado a también ser $O(1)$?

Edit: Considere los dos casos:

Caso 1: $P$ se dibuja de manera uniforme y en forma independiente de la unidad de la plaza.

Caso 2: $P$ se dibuja de manera uniforme y en forma independiente de la unidad de disco.

Hay resultados conocidos de punto conjuntos con otras distribuciones? Cualquier referencia valiosa sobre esta pregunta?

Answer 1

No sé si he entendido bien, yo tampoco sé la probabilidad de espacio (es decir, si $P$ es al azar en $\mathbb{R}^2$, y si sí, entonces ¿cuál es la distribución). Sin embargo, si $P$ es fijo, entonces la respuesta es probablemente no, es decir, el grado medio (para cualquier triangulaciones de Delaunay) puede ser arbitrariamente alta. Simplemente tome $P$ regular $(n-3)$-gon y añadir 3 más puntos que el resto será estrictamente contenida en el triángulo resultante, que significa que el casco convexo de $P$ serán los tres puntos. En cualquier triangulación cada punto de la circunferencia se tiene que conectarse a un punto de los de casco, y sólo hay $O(1)$ de ellos, por lo que el promedio de grado debe ser alta.

Answer 2

No es claro para mí si te refieres al grado medio de los vértices del casco convexo o la suma de los grados de los vértices del casco convexo. En este último caso el hecho de que el número esperado de vértices en el casco convexo es $O(\log n)$ haría un $O(1)$ destino sorprendente.

Answer 3

Tengo una intuitiva argumento de por qué el grado medio del casco vértices debe todavía ser $O(1)$ cuando el punto de ajuste se dibuja de manera uniforme desde una convexidad (como una unidad cuadrada o unidad de disco).

El entorno del casco vertex es mucho "el mismo" que el interno vértices con respecto a los cerca de otros vértices, excepto que no hay vértices a un lado de ella. Dicho de otra manera, si me tomo algo de convexidad y generar puntos de manera uniforme en el interior, a continuación, cortar por la mitad y tirar todos los puntos de un lado, el punto resultante del conjunto como bien provienen de una distribución uniforme en la nueva forma, pero algunos puntos que fueron previamente interna vértices son ahora casco vértices, y la distribución de puntos en uno de los lados es el mismo que era antes, cuando eran interna de los vértices. Esto significa que el casco vértices no tiene que preocuparse acerca de vecino puntos están más cerca o más lejos de lo normal, sólo que la distribución es en un solo lado.

Bueno, por lo que los puntos de "look" de la misma en un casco de vértice, pero no son sólo la mitad de los muchos y todos ellos están en un lado. Pero, ¿qué acerca de los bordes? Seguramente como un casco vertex, más bordes vendrá a ellos que si estaban profundamente en el medio. Así, podemos estimar los bordes en el casco buena aproximación a la consideración de la "sub-casco", que yo defino como $\operatorname{conv}(P-\operatorname{conv}(P))$, es decir, los puntos en el casco convexo de los puntos que quedan después de eliminar el verdadero casco convexo de los puntos. Estos son los "lejana", los puntos que forman los bordes con el casco puntos, simplemente porque no hay más puntos en el otro lado del casco para conectarse.

Hay $O(\log n)$ casco puntos y $O(n)$ puntos, por lo $|P-\operatorname{conv}(P)|$ $O(n)$ y el sub-casco también es $O(\log n)$. Por lo tanto (estoy ignorando una gran cantidad de variables, porque yo soy sólo después de que un gran$O$ estimado) no será, en promedio, $O(1)$ conexiones desde adyacentes casco puntos y sub-casco puntos, y $O(1)$ cerca de puntos (este es el factor interno vértices tienen, tal vez, dividido por $2$), para un total de $O(1)$ bordes en un típico casco punto.

Nota: Esto no es ni siquiera cerca de una prueba matemática, pero se debe dar por lo menos una fuerte evidencia para creer que el casco vértices tienen $O(1)$ grado medio.