Ir a navegaciónSaltar a buscar
El círculo punteado es el contorno de la esfera vacía más grande en el empaquetamiento compacto de esferas . Consulte también Defecto intersticial .
Encontrar el círculo vacío más grande usando el diagrama de Voronoi (dos soluciones).
En geometría computacional , el mayor problema de esferas vacías es el problema de encontrar una hiperesfera de mayor radio en el espacio d -dimensional cuyo interior no se superpone con ningún obstáculo dado.
Dos dimensiones
El mayor problema de círculo vacío es el problema de encontrar un círculo de mayor radio en el plano cuyo interior no se superpone con ningún obstáculo dado.
Un caso especial común es el siguiente. Dados n puntos en el plano, encuentre un círculo más grande centrado dentro de su casco convexo y que no encierre ninguno de ellos. El problema puede resolverse utilizando diagramas de Voronoi en el tiempo óptimo. . [1] [2]
Ver también
Referencias
- ^ GT Toussaint, "Computación de los círculos vacíos más grandes con restricciones de ubicación", Revista Internacional de Ciencias de la Información y la Computación , vol. 12, núm. 5, octubre de 1983, págs. 347-358.
- ^ Megan Schuster, "El mayor problema del círculo vacío"