En geometría computacional y teoría de grafos geométricos , un β -esqueleto o esqueleto beta es un grafo no dirigido definido a partir de un conjunto de puntos en el plano euclidiano . Dos puntos p y q están conectados por una arista siempre que todos los ángulos prq sean más agudos que un umbral determinado a partir del parámetro numérico β .
Sea β un número real positivo y calcule un ángulo θ utilizando las fórmulas
Para dos puntos cualesquiera p y q en el plano, sea R pq el conjunto de puntos para los cuales el ángulo prq es mayor que θ . Entonces R pq toma la forma de una unión de dos discos abiertos con diámetro βd ( p , q ) para β ≥ 1 y θ ≤ π/2, y toma la forma de la intersección de dos discos abiertos con diámetro d ( p , q )/ β para β ≤ 1 y θ ≥ π/2. Cuando β = 1 las dos fórmulas dan el mismo valor θ = π/2, y R pq toma la forma de un solo disco abierto con pq como su diámetro.
El β -esqueleto de un conjunto discreto S de puntos en el plano es el grafo no dirigido que conecta dos puntos p y q con una arista pq siempre que R pq no contenga puntos de S . Es decir, el β -esqueleto es el grafo de región vacía definido por las regiones R pq . [1] Cuando S contiene un punto r para el cual el ángulo prq es mayor que θ , entonces pq no es una arista del β -esqueleto; el β -esqueleto consiste en aquellos pares pq para los cuales no existe tal punto r .
Algunos autores utilizan una definición alternativa en la que las regiones vacías R pq para β > 1 no son uniones de dos discos sino más bien lentes (más a menudo llamadas en este contexto " lunes "), intersecciones de dos discos congruentes con diámetro βd ( pq ), tales que el segmento de línea pq se encuentra en un radio de ambos discos y tal que los puntos p y q se encuentran ambos en el límite de la intersección. Al igual que con el β -esqueleto basado en círculo , el β -esqueleto basado en lune tiene una arista pq siempre que la región R pq esté vacía de otros puntos de entrada. Para esta definición alternativa, el grafo de vecindad relativa es un caso especial de un β -esqueleto con β = 2. Las dos definiciones coinciden para β ≤ 1, y para valores mayores de β el esqueleto basado en círculo es un subgrafo del esqueleto basado en lune.
Una diferencia importante entre los β- esqueletos basados en círculos y en lúmenes es que, para cualquier conjunto de puntos que no se encuentre en una sola línea, siempre existe un valor suficientemente grande de β tal que el β -esqueleto basado en círculos es el grafo vacío . Por el contrario, si un par de puntos p y q tiene la propiedad de que, para todos los demás puntos r , uno de los dos ángulos pqr y qpr es obtuso, entonces el β -esqueleto basado en lúmenes contendrá la arista pq sin importar cuán grande sea β .
Los β -esqueletos fueron definidos por primera vez por Kirkpatrick y Radke (1985) como una variación invariante de escala de las formas alfa de Edelsbrunner, Kirkpatrick y Seidel (1983). El nombre, " β -esqueleto", refleja el hecho de que en cierto sentido el β -esqueleto describe la forma de un conjunto de puntos de la misma manera que un esqueleto topológico describe la forma de una región bidimensional. También se han considerado varias generalizaciones del β -esqueleto a grafos definidos por otras regiones vacías. [1] [2]
Si β varía continuamente de 0 a ∞, los β -esqueletos basados en círculos forman una secuencia de grafos que se extienden desde el grafo completo hasta el grafo vacío . El caso especial β = 1 conduce al grafo de Gabriel , que se sabe que contiene el árbol de expansión mínimo euclidiano ; por lo tanto, el β -esqueleto también contiene el grafo de Gabriel y el árbol de expansión mínimo siempre que β ≤ 1.
Para cualquier constante β , se puede utilizar una construcción fractal que se asemeje a una versión aplanada del copo de nieve de Koch para definir una secuencia de conjuntos de puntos cuyos β -esqueletos son caminos de longitud arbitrariamente grande dentro de un cuadrado unitario. Por lo tanto, a diferencia de la triangulación de Delaunay estrechamente relacionada , los β -esqueletos tienen un factor de estiramiento ilimitado y no son llaves geométricas . [3]
Un algoritmo ingenuo que prueba cada triple p , q y r para determinar la pertenencia de r a la región R pq puede construir el β -esqueleto de cualquier conjunto de n puntos en el tiempo O( n 3 ).
Cuando β ≥ 1, el β -esqueleto (con cualquiera de las dos definiciones) es un subgrafo del grafo de Gabriel, que es un subgrafo de la triangulación de Delaunay . Si pq es una arista de la triangulación de Delaunay que no es una arista del β -esqueleto, entonces un punto r que forma un ángulo grande prq puede encontrarse como uno de los dos puntos que forman un triángulo con p y q en la triangulación de Delaunay. Por lo tanto, para estos valores de β , el β -esqueleto basado en círculos para un conjunto de n puntos puede construirse en tiempo O( n log n ) calculando la triangulación de Delaunay y usando esta prueba para filtrar sus aristas. [2]
Para β < 1, un algoritmo diferente de Hurtado, Liotta y Meijer (2003) permite la construcción del β -esqueleto en tiempo O( n 2 ). No es posible un límite temporal mejor para el peor de los casos porque, para cualquier valor fijo de β menor que uno, existen conjuntos de puntos en posición general (pequeñas perturbaciones de un polígono regular ) para los cuales el β -esqueleto es un grafo denso con un número cuadrático de aristas. En el mismo límite temporal cuadrático, también se puede calcular todo el β -espectro (la secuencia de β -esqueletos basados en círculos formados al variar β ).
El β -esqueleto basado en círculos se puede utilizar en el análisis de imágenes para reconstruir la forma de un objeto bidimensional, dado un conjunto de puntos de muestra en el límite del objeto (una forma computacional del rompecabezas de conectar los puntos donde la secuencia en la que se deben conectar los puntos debe deducirse mediante un algoritmo en lugar de darse como parte del rompecabezas). Aunque, en general, esto requiere una elección del valor del parámetro β , es posible demostrar que la elección β = 1,7 reconstruirá correctamente todo el límite de cualquier superficie lisa y no generará ningún borde que no pertenezca al límite, siempre que las muestras se generen de manera suficientemente densa en relación con la curvatura local de la superficie. [4] Sin embargo, en pruebas experimentales, un valor menor, β = 1,2, fue más efectivo para reconstruir mapas de calles a partir de conjuntos de puntos que marcan las líneas centrales de las calles en un sistema de información geográfica . [5] Para generalizaciones de la técnica del β -esqueleto para la reconstrucción de superficies en tres dimensiones, consulte Hiyoshi (2007).
Los β -esqueletos basados en círculos se han utilizado para encontrar subgrafos de la triangulación de peso mínimo de un conjunto de puntos: para valores suficientemente grandes de β , se puede garantizar que cada arista del β -esqueleto pertenece a la triangulación de peso mínimo. Si las aristas encontradas de esta manera forman un grafo conectado en todos los puntos de entrada, entonces las aristas de triangulación de peso mínimo restantes se pueden encontrar en tiempo polinomial mediante programación dinámica . Sin embargo, en general, el problema de triangulación de peso mínimo es NP-hard, y el subconjunto de sus aristas encontrado de esta manera puede no estar conectado. [6]
Los β -esqueletos también se han aplicado en el aprendizaje automático para resolver problemas de clasificación geométrica [7] y en redes inalámbricas ad hoc como un mecanismo para controlar la complejidad de la comunicación mediante la elección de un subconjunto de los pares de estaciones inalámbricas que pueden comunicarse entre sí. [8]
