Kann man in subquadratischer Zeit den Punkt finden, der allen Punkten am nächsten ist?

Question

Eine algorithmische Frage.

Input:

• eine Liste von Datenpunkten X
• Eine metrische Funktion für die Datenpunkte dist(x,y), die O (1) Zeit zu bewerten und gehorcht der Dreiecksungleichung

Ist dauert es ein Algorithmus, der einen Vektor von Datenpunkten Y zurückgeben kann, so dass Y[i] der nächstgelegene Punkt in X zu X[i] in subquadratischer Zeit ist?

Offensichtlich ist dies in O (n^2) möglich, weil Sie einfach jeden Punkt direkt überprüfen können. Ich frage mich, ob es vielleicht möglich ist, die Dreiecksungleichheit zu nutzen, um dies zu verbessern. Ich wäre auch an Näherungsalgorithmen mit nachweisbaren Schranken interessiert (d. H. Etwas wie Y[i] ist nicht mehr als (1 + log (n)) mal der Abstand von X[i] als Minimum).

Answer 1

Es gibt keinen solchen Algorithmus. Man betrachte eine Metrik, bei der alle außer einem Punktepaar die Entfernung 1 haben. Dieses Paar kann nicht gefunden werden, ohne seine spezielle Distanz-Orakel-Eingabe zu berücksichtigen, die im schlimmsten Fall Omega (n^2) -Abfragen erfordert.

Cover trees kann verwendet werden, um das Problem der genauen Nachbarn zu lösen. Die Zeitgrenze hängt von der sogenannten Doppeldimension der Metrik ab.