En geometría computacional y teoría geométrica de grafos, un esqueleto β (o también esqueleto beta) es un grafo definido a partir de un conjunto de puntos en el plano mediante un criterio angular. 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 por el parámetro numérico β.
Dado β un número real positivo, se calcula el ángulo θ usando las fórmulas:
Para dos puntos cualesquiera p y q en el plano, sea Rpq el conjunto de puntos para los cuales el ángulo prq es mayor que θ. Entonces, Rpq toma la forma de la 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, ambas fórmulas dan el mismo valor θ=π/2, y Rpq toma la forma de un único disco abierto con pq como diámetro.
El esqueleto β de un conjunto discreto S de puntos en el plano es el grafo que conecta dos puntos p y q con una arista pq siempre que Rpq no contenga ningún punto de S. Es decir, el esqueleto β es el grafo de región vacía definido por las regiones Rpq. 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 β consta de los pares pq para los cuales no existe tal punto r.
Algunos autores utilizan una definición alternativa en la que las regiones vacías Rpq para β>1 no son uniones de dos discos, sino lúnulas, intersecciones de dos discos congruentes con diámetro βd(pq), de modo que el segmento recto pq se encuentra sobre un radio de ambos discos y los puntos p y q se encuentran en el límite de la intersección. Al igual que con el β-esqueleto basado en círculos, el β-esqueleto basado en lúnulas tiene una arista pq siempre que la región Rpq esté vacía de otros puntos del conjunto 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írculos es un subgrafo del esqueleto basado en lúnulas.
Una diferencia importante entre los esqueletos β basados en círculos y en lúnulas es que, para cualquier conjunto de puntos que no se encuentre sobre una sola línea recta, siempre existe un valor suficientemente grande de β tal que el esqueleto β basado en círculos es el grafo nulo. En cambio, 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únulas contendrá la arista pq independientemente del valor de β.
Los esqueletos β fueron definidos por primera vez por Kirkpatrick y Radke (1985) como una variación independiente de la escala de las formas alfa de Edelsbrunner, Kirkpatrick y Seidel (1983). El nombre "esqueleto β" refleja 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.
Si β varía continuamente de 0 a 8, los esqueletos β basados en círculos forman una secuencia de grafos que se extiende desde el grafo completo hasta el grafo nulo. El caso especial β=1 conduce al grafo de Gabriel, que se sabe que contiene el árbol de extensión mínima euclídea. Por lo tanto, el esqueleto β también contiene el grafo de Gabriel y el árbol de expansión mínima siempre que β=1.
Para cualquier β constante, se puede usar una construcción fractal similar 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 factores de estiramiento no acotados y no son árboles de extensores geométricos.
Un algoritmo que prueba cada triplete p, q y r para determinar si r pertenece a la región Rpq puede construir el esqueleto β de cualquier conjunto de n puntos en tiempo O(n3).
Cuando β=1, el esqueleto β (con cualquiera de las definiciones) es un subgrafo del grafo de Gabriel, que a su vez 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 se puede encontrar un punto r que forme un ángulo grande prq como uno de los dos puntos que, como máximo, 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 se puede construir en tiempo O(n log n) calculando la triangulación de Delaunay y utilizando esta prueba para filtrar sus aristas.
Para β, < 1, un algoritmo diferente de Hurtado, Liotta y Meijer (2003) permite la construcción del esqueleto β en tiempo O(n2). No es posible una mejor cota de tiempo en 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 intervalo de tiempo cuadrático, también se puede calcular el espectro completo de β (la secuencia de esqueletos β basados en círculos formados al variar β).
El esqueleto β basado en círculos se puede utilizar en análisis de imágenes para reconstruir la forma de un objeto bidimensional, dado un conjunto de puntos de muestra en el contorno del objeto (una forma computacional del rompecabezas une los puntos, donde la secuencia en la que se conectan los puntos debe deducirse mediante un algoritmo en lugar de estar dada como parte del rompecabezas). Aunque, en general, esto requiere elegir el valor del parámetro β, es posible demostrar que la elección β = 1,7 reconstruirá correctamente todo el contorno de cualquier superficie lisa, sin generar bordes que no pertenezcan al contorno, siempre que las muestras se generen con la densidad suficiente en relación con la curvatura local de la superficie. Sin embargo, en pruebas experimentales, un valor menor, β = 1,2, resultó más eficaz para reconstruir mapas de calles a partir de conjuntos de puntos que marcan los ejes centrales de las calles en un sistema de información geográfica. Para generalizaciones de la técnica del esqueleto β a la reconstrucción de superficies en tres dimensiones, véase Hiyoshi (2007).
Se han utilizado esqueletos β basados en círculos para encontrar subgrafos de la triangulación de peso mínimo de un conjunto de puntos: para valores suficientemente grandes de β, se garantiza que cada arista del esqueleto β pertenece a la triangulación de peso mínimo. Si las aristas encontradas de esta manera forman un grafo conexo en todos los puntos de entrada, entonces las aristas restantes de la triangulación de peso mínimo pueden encontrarse en tiempo polinómico mediante programación dinámica. Sin embargo, en general, el problema de la triangulación de peso mínimo es NP-difícil, y el subconjunto de sus aristas encontradas de esta manera puede no estar conectado.
Los esqueletos β también se han aplicado en aprendizaje automático para resolver problemas geométricos de clasificación y en redes ad hoc inalámbricas como mecanismo para controlar la complejidad de la comunicación mediante la elección de un subconjunto de pares de estaciones inalámbricas que pueden comunicarse entre sí.
| Control de autoridades |
|
|---|
Datos: Q4897306