4 votos

Comprensión McMullen ' Teorema del límite superior de s

Soy un estudiante de informática trabajando en un documento sobre limitada triangulaciones de delaunay. He estado buscando una prueba con respecto a la cota superior para el número de triángulos en una limitada triangulaciones de delaunay con $n$ vértices y me las arreglé para encontrar este papel:

http://www.cs.ucdavis.edu/~amenta/pubs/HiDeeDel.pdf

Proporciona un límite superior en el número de triángulos en una triangulación de delaunay (yo estaba buscando restringido) el uso de McMullen del límite Superior Teorema (http://www.ifor.math.ethz.ch/teaching/lectures/poly_comp_ss11/lecture7). El documento no describe su técnica para encontrar el límite superior de McMullen del teorema en profundidad, así que me veo obligado a descubrirlo por mí mismo.

Aquí está el problema. Casi no tengo la matemática y la geometría de fondo del pasado cálculo vectorial y probabilidad (mis fortalezas se encuentran en la matemática discreta y teoría de grafos), por lo que no puedo entender lo que McMullen del teorema de medios. Tengo una corazonada de que puede ser aplicado arbitraria de las triangulaciones (no sólo DTs), pero no estoy seguro de cómo iba a ir sobre mostrar esto.

Además, realmente la atención acerca de la 2-dimensional caso.

2voto

Kundor Puntos 3534

McMullen del límite superior teorema realmente no dice nada en el caso planar. Resulta útil sólo para las "triangulaciones" (es decir, una división en simplices) en más de espacio tridimensional. Como tú supones, se aplica a cualquier triangulación.

En primer lugar usted debe ver la conexión entre las triangulaciones y polytopes. Considere la posibilidad de una triangulación en el plano. Si usted se imagina que se dibuja en la superficie de un globo, luego todo el espacio "fuera" de la triangulación es sólo la otra cara (voy a llamar a la cara exterior.) Usted puede reducir hacia abajo por la cara exterior. Siempre es posible para "completar" la triangulación, añadir bordes si es necesario, de modo que la cara exterior es también un triángulo; a continuación, cuando usted lo pone en un globo, tiene un poliedro con caras triangulares.

Usted puede hacer esto con más dimensiones triangulaciones así: Cualquier triangulación en $d$-espacio, junto con su cara exterior, es el conjunto de caras de una $(d+1)$-dimensiones polytope.

McMullen del límite Superior Teorema da el número máximo de $i$-se enfrenta a una $d$-dimensiones polytope con $n$ vértices posiblemente puede tener ($i$- cara es una cara de la dimensión $i$, por lo tanto, 0-caras vértices, 1-caras son bordes, etc.) Desde las triangulaciones son polytopes, también le da un límite superior en el número de $i$-caras en una triangulación con $n$ vértices. Decir $f_i$ es el número de $i$-caras; luego, el teorema dice

$$ f_i \leq \binom{n}{i+1} \quad \text{ si } 0 \leq i \leq \left\lfloor\frac{d-2}{2}\right\rfloor. $$

Los límites superiores en el número de $i$-se enfrenta con $i \geq \lfloor\frac{d}{2}\rfloor$ a continuación, se determinan por la Dehn-Sommerville ecuaciones.

Para un plano de la triangulación, estamos preocupados con un 3-dimensional polytope (aka poliedro), por lo que el límite Superior Teorema dice $f_0 \leq n$, es decir, una triangulación con $n$ vértices tiene en la mayoría de las $n$ vértices, lo cual no es muy útil. El Dehn-Sommerville ecuaciones dirá que $3 f_2 = 2 f_1$$f_0 - f_1 + f_2 = 2$, a partir de la cual se puede concluir que el número de aristas $f_1 = 3n - 6$ y el número de triángulos $f_2 = 2n - 4$. Tenga en cuenta que esto es sólo después de completar la triangulación, si es necesario, de modo que la cara exterior es también un triángulo, y el recuento de la cara exterior como uno de los rostros en $f_2$.

McMullen del teorema también se da una construcción explícita de un $d$-polytope con $n$ vértices con el que se consigue el máximo número de $i$-caras, para cada $i$: es decir, tomar cualquier $n$ puntos en la curva de $(t,t^2,t^3,\dotsc,t^d)$ por sus vértices.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X