Dado un conjunto de puntos en el espacio 2D P, donde Pi = (Xi, Yi),encontrar un punto tal que la distancia máxima a cualquier punto en un conjunto de puntos P se minimiza
Necesito encontrar un punto objetivo T tal que la distancia máxima a cualquier Pi se minimiza.
T no tiene por qué existir en P, y se puede definir de manera arbitraria
¿Existe un algoritmo que pueda usar para esto?
Este es el smallest circle problem.
sí, esto es básicamente lo que quiero, excepto que no necesito el radio, solo necesito el punto central. – jdeuce
El artículo de wikipedia contiene un algoritmo de tiempo lineal para resolver este problema. Dudo mucho que no requerir un radio en la salida permita soluciones más rápidas. –
sí, el papel es difícil de leer, ¿tienes algún seudocódigo para el alg? – jdeuce
http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/problem.html
que esto puede ser una solución a su problema con la explicación bastante buena, pero es O (n^2)
El problema es que el enlace al algoritmo real está roto. Pero un buen gráfico en vivo para representar el algoritmo. – Paparazzi
no he probado, pero creo que la solución es simplemente:
(min (Xi) + max (Xi))/2, (min (Yi) + max (Yi))/2)
en realidad esta es una aproximación. imagine un cuadrado alrededor del círculo más pequeño, la cantidad máxima que puede ser la aproximación es la distancia desde la esquina del cuadrado al círculo. – jdeuce
Cualquiera o suma no será el mismo punto. – Paparazzi
¿Por qué no es óptimo? –
Actualicé la pregunta para deshacerme de la referencia a la solución aproximada que estaba usando, ya que es irrelevante para la discusión. – jdeuce