¿Encuentra el punto central en un conjunto de puntos de espacio métrico, en menos de

Tengo un conjunto de puntos que se definen en un espacio métrico, por lo que puedo medir una 'distancia' entre puntos, pero nada más. Quiero encontrar el punto más central dentro de este conjunto, que defino como el punto con la suma mínima de distancias a todos los demás puntos. El cálculo métrico es lento, por lo que debe evitarse siempre que sea posible. $n$

La forma obvia de encontrar este punto utiliza cálculos de distancia métrica, ya que simplemente (a) calcula para cada punto la suma de distancias a todos los demás puntos y luego (b) toma el punto mínimo. $n^2$

¿Hay alguna manera de hacer esto en menos de comparaciones de distancia? (Probablemente haciendo uso de la desigualdad del triángulo de alguna manera, lo que debería ser compatible con mi métrica). $O(n^2)$

Una buena aproximación podría ser suficiente si no existe un método exacto.

complexity-theory computational-geometry lower-bounds search-problem Logística de puertas abiertas
fuente

Sin la desigualdad del triángulo (o alguna otra forma de obtener información sobre los bordes no medidos),

es la única solución; Esto puede verse por un argumento antagonista.

O (n^{2})

$O(n^2)$

Kittsil

Suponga que la desigualdad del triángulo está disponible, debería ser para mi métrica.

Open Door Logistics

Esto es esencialmente calcular las radios de un gráfico con igualdad triangular.

Kaveh

@Kaveh Supongo que te refieres al radio ... a menos que el gráfico tenga un borde roto. Me estoy asegurando de que hay demasiado vocabulario que no sé. --- Pero entonces es un gráfico completo, y el tamaño de entrada es solo el número de vértices.

babou

@OpenDoorLogistics Si no tiene la desigualdad del triángulo, no es un espacio métrico, por definición. Aclare la pregunta: si sabe que es un espacio métrico, entonces sabe que tiene la desigualdad del triángulo; Si no sabe que tiene la desigualdad del triángulo, no puede afirmar que es un espacio métrico.

David Richerby

Respuestas:

$\Theta(n^2)$

$1$ $0.9$ $1.0$ $1.1$

$\mathbb{R}^d$ $O((d+1)n)$ $d+1$

$d+1$ $P$ $P$ $P$ $P$ $P$ $O(n^2)$

DW
fuente

n

$n$

n - 1

$n-1$

Θ (n^{2})

$\Theta(n^2)$

n

$n$

@DW Gracias, ¿podríamos hacer algo mejor en el caso promedio? Esto está motivado por un problema del mundo real, por lo que es probable que los datos sean 'promedio' (lo que sea que eso signifique).

Open Door Logistics

@todos - disculpas por la confusión re: métrica (soy un laico en CS teórica). Mi función de distancia definitivamente obedece los 4 criterios para un espacio métrico, según la definición de Wikipedia de un enlace de espacio métrico .

Open Door Logistics

@OpenDoorLogistics, agregué un caso especial en el que parece posible hacerlo mejor.

Vea el trabajo de Piotr Indyk sobre algoritmos rápidos para espacios métricos. ( Algoritmos sublineales para problemas de espacio métrico , en Proceedings of STOC '99 , pp.428–434. ACM, 1999; PS ) La Sección 3 proporciona un algoritmo de 1 mediana aproximada de tiempo lineal.

usuario71641
fuente

¿Podría dar un resumen del algoritmo? Lo ideal es buscar respuestas completas, en lugar de enlaces a contenido externo.

David Richerby

Disculpas por la muy lenta respuesta. Obviamente no reviso StackExchange muy a menudo. Creo que me tomaría más de una hora escribir un resumen decente a mitad de camino, mientras que el artículo de Piotr está bellamente escrito, explica el algoritmo de manera muy clara y tiene todas las definiciones precisas al lado. Por lo tanto, personalmente recomendaría encarecidamente hacer uso de este contenido externo de alta calidad, en lugar del contenido interno de calidad media que podría producir. La respuesta corta es: si está dispuesto a encontrar una mediana aproximada, puede hacerlo en tiempo lineal O (n).

user71641