He dado algunos puntos (coordenadas 2D) y quiero encontrar el círculo más pequeño, que incluye todos estos puntos. El algoritmo no tiene que ser muy eficiente (aunque sería agradable naturalmente).¿Cómo puedo encontrar el círculo mínimo que incluye algunos puntos dados?
El enlace es muy interesante, pero los resultados mencionados allí no están actualizados. El algoritmo de Nimrod Megiddo de 1983 es una solución de tiempo lineal, pero hay algoritmos mucho más prácticos, como el de Welzl, ver [esta respuesta] (http://stackoverflow.com/a/17329529/734191). – Hbf
Ésta es la llamada más pequeño que encierra bolas problema (en su caso, Encerrando círculo más pequeño), también denominado Miniball. Hay varios algoritmos e implementaciones que hay para este problema - todos de los siguientes son soluciones en tiempo lineal (es decir, dados n bolas, corren en O (n) si se tiene en cuenta la dimensión d fijo, d = 2 en su caso):
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 necesita usar todo el CGAL, simplemente extraiga el encabezado requerido y los archivos fuente).
Posible duplicado de [Círculo más pequeño que cubre determinados puntos en el plano 2D] (http://stackoverflow.com/questions/4901535/smallest-circle-which-covers-given-points-on-2d-plane); hay una respuesta idéntica del mismo usuario, y la otra pregunta tiene una mejor redacción, en mi opinión. La respuesta de solo enlace en esta versión tampoco es excelente ... – Benjamin