Problema del mayor círculo vacío

Mayor círculo vacío (en rojo) de un conjunto de puntos, con centro interior al cierre convexo (en azul)
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".[1]​

El problema fue enunciado por James Joseph Sylvester en 1857, y él mismo publicó un estudio sobre el problema tres años después.[2]​ 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.[3]​[4]​[5]​[6]​

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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «http://localhost:6011/es.wikipedia.org/v1/»:): {\displaystyle 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.[1]​[7]​
  • 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.

Referencias y enlaces externos

  1. ↑ a b Toussaint, Godfried (1983). «Computing largest empty circles with location constraints». International Journal of Computer & Information Sciences 12 (5): 347-358. doi:10.1007/BF01008046. 
  2. ↑ Eiselt, H. A. (2011). Foundations of Location Analysis (en inglés). Springer Science & Business Media. p. 64. 
  3. ↑ Morales, Miguel Ángel (27 de junio de 2011). «Una interesante introducción a la Geometría Computacional». Gaussianos. Consultado el 1 de marzo de 2017. 
  4. ↑ Grima, Clara (2011). «Cada uno en su región y Voronoi en la de todos». Naukas. 
  5. ↑ Franco P. Preparata y Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6. 
  6. ↑ Chew, Paul (1986). «Finding largest empty circles with location constraints». Technical Report. TR86-130. 
  7. ↑ Megan Schuster, "The Largest Empty Circle Problem"