Grafos que "poligonizan" una variedad

Question

Es bastante fácil conceptualizar una cobertura del Plano euclidiano por un conjunto contable de polígonos convexos pero de tamaño y forma arbitrarios (vistos como subconjuntos del plano) sin solapamientos. Se puede exigir -¿sin pérdida de generalidad? - que dos polígonos compartan exactamente una arista completa o ninguna.

¿Existe un nombre oficial para dicho revestimiento?

Supongo que la "poligonización del plano" no es del todo errónea, pero pasa por alto algunos aspectos: la convexidad y la unicidad de las aristas compartidas.

En fin: una poligonización del plano induce un grafo (infinito) con vértices y aristas evidentes.

(¿Cómo) puede caracterizarse un gráfico de este tipo?
("Un grafo es inducido por una poligonización del plano si es plano, Conectado por 2 bordes y ...")

El plano euclidiano no es el único colector que puede poligonizarse del modo descrito anteriormente: existen poligonizaciones de la esfera, el toroide, etcétera, etcétera.

(Cómo) se pueden caracterizar los gráficos que poligonizan cualquier ¿Múltiple?

Answer 1

Podría equivocarme pero lo que el concepto que buscas se parece bastante a un Diagrama de Voronoi .

Un extracto de Wikipedia:

En matemáticas, un diagrama de Voronoi i regiones basadas en la distancia a puntos en un subconjunto específico del plano. Ese conjunto de puntos (llamados semillas, sitios o generadores) se especifica de antemano, y para cada semilla hay una región correspondiente formada por todos los puntos más cercanos a esa semilla que a cualquier otra. Estos regiones se denominan celdas de Voronoi. El diagrama de Voronoi de un conjunto de puntos puntos es doble a su triangulación de Delaunay.

Y así es como se ve (créditos a Wikipedia):

Existe un algoritmo bastante fácil de seguir para generar un diagrama de Voronoi de un espacio dado. Básicamente necesitarás una "semilla" de puntos para hacer las particiones. Pueden ser aleatorios, por lo que las celdas serán aleatorias cada vez que apliques el procedimiento desde cero.

Hace algún tiempo yo también estaba tratando de entender cómo se aplica, aquí está un diagrama de Voronoi de un atractor de Sierpinski .