Problema: ¿Cuál es el diámetro más pequeño posible de un círculo que cubre determinados N puntos en un plano 2D?Círculo más pequeño que cubre puntos determinados en el plano 2D
¿Cuál es el algoritmo más eficiente para resolver este problema y cómo funciona?
Este es el smallest circle problem. Ver las referencias de los enlaces a los algoritmos sugeridos.
E.Welzl discos, el más pequeño que encierra (bolas y elipsoides), en H. Maurer (Ed.), Nuevos Resultados y nuevas tendencias en Ciencias de la Computación, Lecture Notes in Computer Science , vol. 555, Springer-Verlag, 359-37 (1991)
es la referencia al algoritmo de "más rápido".
¡Gracias! Supongo que esta respuesta se puede incluir en la pregunta original para eliminar el duplicado. – Leonid
Existen varios algoritmos e implementaciones para el problema de bolas más pequeñas problema.
Para 2D y 3D, Gärtner's implementation es probablemente la más rápida.
Para dimensiones superiores (hasta 10.000, por ejemplo), consulte https://github.com/hbf/miniball, que es la implementación de un algoritmo por Gärtner, Kutz y Fischer (nota: soy uno de los coautores).
Para dimensiones muy, muy altas, core-set (aproximación) los algoritmos serán más rápidos.
Nota: Si usted está buscando un algoritmo para calcular la esfera más pequeña que encierra de esferas, se encuentra una aplicación C++ en el Computational Geometry Algorithms Library (CGAL). (No es necesario utilizar todos CGAL, basta con extraer los archivos de cabecera y de origen necesarios.)
el enfoque de diagrama de puntos de Voronoi más alejado
http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html
resulta que trabajar muy bien para el problema 2 d. No es iterativo y (bastante seguro) garantiza exactamente. Sospecho que no se extiende tan bien a las dimensiones más altas, por lo que hay poca atención en la literatura.
Si hay interés lo describiré aquí - el enlace de arriba es un poco difícil de entender, creo.
editar otro enlace: http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6704
Esto se ha hecho antes. Si solo pudiera encontrarlo. –
Este debería ser el __Círculo más pequeño__, échele un vistazo aquí: http://en.wikipedia.org/wiki/Smallest_circle_problem – Jack
Aquí está el "duplicado", aunque como el mío no es una respuesta fantástica: http: // stackoverflow. com/questions/3102547/how-can-i-find-the-minimal-circle-include-some-given-points – Benjamin