Problema del mayor círculo vacío

Archivo:Largest Empty Circle.svg

Mayor círculo vacío (en rojo) de un conjunto de puntos, con centro interior al cierre convexo (en azul)

Error al crear miniatura:

Uso del Diagrama de Voronoi para encontrar el mayor círculo vacío (dos soluciones).

En geometría computacional, el problema del mayor círculo vacío es un problema cuyo enunciado es: "Dados n puntos en un espacio métrico, se pide encontrar el círculo de mayor radio cuyo centro esté en el interior del cierre convexo de los puntos y que no contenga ninguno en su interior".

El problema fue enunciado por James Joseph Sylvester en 1857, y él mismo publicó un estudio sobre el problema tres años después. Tiene aplicaciones en procesos de planificación de recursos, donde debamos elegir una ubicación en el interior de un área que esté lo más alejada posible de una serie de puntos. Por ejemplo, la ubicación de un vertedero lo más alejado posible de los centros de población de la zona.

Análisis del problema en 2D

Este problema puede solucionarse de forma sencilla mediante la construcción del diagrama de Voronoi o la triangulación de Delaunay del conjunto de puntos de entrada. Como la construcción de cualquiera de estas dos estructuras requiere un tiempo proporcional a $O(n\log n)$, esta es la cota del problema.

• En caso de emplear el Diagrama de Voronoi, la solución siempre tendrá su centro en uno de los vértices del diagrama, o bien en alguna de las intersecciones de las aristas del diagrama con el cierre convexo del conjunto.
• En caso de emplear una triangulación de Delaunay, el mayor círculo vacío será uno de los círculos circunscritos a alguno de los triángulos de Delaunay. Hay que poner atención, porque algunos de estos círculos tienen su centro en el exterior del cierre convexo, y por lo tanto necesitan una corrección de su radio y posición del centro (que debe ser proyectado sobre el cierre convexo). Por ello, generalmente se toma la opción de emplear el diagrama de Voronoi.