esqueleto beta
En geometría computacional y teoría de grafos geométricos , un esqueleto β o esqueleto beta es un gráfico 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 β .
Para cualesquiera dos puntos 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 la unión de dos discos abiertos de diámetro βd ( p , q ) para β ≥ 1 y θ ≤ π/2, y toma la forma de la intersección de dos discos abiertos de 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 gráfico 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 gráfico de región vacío 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 un borde del esqueleto β ; elEl esqueleto β consta de aquellos pares pq para los que 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 lentes (más a menudo llamadas en este contexto " lunes "), intersecciones de dos discos congruentes con diámetro βd ( pq ), tal 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 en el límite de la intersección. Al igual que con el esqueleto β basado en círculos, el esqueleto β basado en lune tiene un borde pq siempre que la región R pqestá vacío de otros puntos de entrada. Para esta definición alternativa, el gráfico de vecindad relativa es un caso especial de un esqueleto β con β = 2. Las dos definiciones coinciden para β ≤ 1, y para valores más grandes de β , el esqueleto basado en círculos es un subgrafo de la lune- esqueleto basado.
Una diferencia importante entre los esqueletos β basados en círculos y los basados en lunas 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 gráfico 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 lune contendrá el borde pq sin importar qué tan grande sea β es.
Los esqueletos β fueron definidos por primera vez por Kirkpatrick y Radke (1985) como una variación de escala invariable 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 gráficos definidos por otras regiones vacías. [1] [2]
