Finden Sie den Mittelpunkt in einer metrischen Raumpunktmenge in weniger als

Ich habe eine Menge von Punkten, die in einem metrischen Raum definiert sind - so kann ich einen 'Abstand' zwischen Punkten messen, aber sonst nichts. Ich möchte den zentralsten Punkt innerhalb dieser Menge finden, den ich als den Punkt mit der minimalen Summe der Abstände zu allen anderen Punkten definiere. Die Metrikberechnung ist langsam und muss daher nach Möglichkeit vermieden werden. $n$

Der offensichtliche Weg, diesen Punkt zu finden, verwendet metrische Entfernungsberechnungen, da einfach (a) für jeden Punkt die Summe der Entfernungen zu allen anderen Punkten berechnet wird und dann (b) der minimale Punkt genommen wird. $n^2$

Gibt es eine Möglichkeit, dies in weniger als Entfernungsvergleichen zu tun ? (Wahrscheinlich wird die Dreiecksungleichung in irgendeiner Weise ausgenutzt, was mit meiner Metrik übereinstimmen sollte.) $O(n^2)$

Eine gute Annäherung kann ausreichen, wenn keine genaue Methode existiert.

complexity-theory computational-geometry lower-bounds search-problem Open Door Logistics
quelle

Ohne die Dreiecksungleichung (oder eine andere Möglichkeit, Informationen über nicht gemessene Kanten zu erhalten) ist

die einzige Lösung. Dies kann durch ein antagonistisches Argument gesehen werden.

O (n^{2})

$O(n^2)$

Kittsil

Angenommen, die Dreiecksungleichung ist verfügbar - sie sollte für meine Metrik gelten.

Open Door Logistics

Dies berechnet im Wesentlichen die Radios eines Graphen mit Dreiecksgleichheit.

Kaveh

@Kaveh Ich denke du meinst den Radius ... es sei denn, der Graph hat eine gebrochene Kante. Ich stelle sicher, dass es zu viel Vokabular gibt, das ich nicht kenne. --- Aber es ist dann ein vollständiger Graph und die Eingabegröße ist nur die Anzahl der Eckpunkte.

Babou

@OpenDoorLogistics Wenn es keine Dreiecksungleichung gibt, ist es per Definition kein metrischer Raum. Bitte klären Sie die Frage: Wenn Sie wissen, dass es sich um einen metrischen Raum handelt, wissen Sie, dass er die Dreiecksungleichung aufweist. Wenn Sie nicht wissen, dass es die Dreiecksungleichung gibt, können Sie nicht behaupten, dass es sich um einen metrischen Raum handelt.

David Richerby

Antworten:

Nein, im schlimmsten Fall kann man es nicht besser machen als . $\Theta(n^2)$

Stellen Sie sich eine Anordnung von Punkten vor, bei denen jedes Punktepaar einen Abstand von voneinander hat. (Dies ist eine mögliche Konfiguration.) Dann können Sie nichts Besseres tun, als jede Kante zu untersuchen. Insbesondere wenn es eine Kante gibt, die Sie nicht untersucht haben, kann ein Gegner die Länge dieser Kante entweder mit , oder wählen . Alle diese Auswahlmöglichkeiten stimmen mit allen anderen Beobachtungen überein, die Sie gemacht haben, und mit den Anforderungen einer Metrik (z. B. mit der Dreiecksungleichung), sodass alle drei möglich sind. Sie erfordern jedoch unterschiedliche Ausgänge. Wenn Ihr Algorithmus diese Kante nicht untersucht und dann etwas ausgibt, kann ein Gegner immer eine Länge für die nicht untersuchte Kante auswählen, die die Ausgabe Ihres Algorithmus falsch macht. $1$ $0.9$ $1.0$ $1.1$

Wenn Sie jedoch wissen, dass alle Punkte in (obwohl Sie nicht ihre Koordinaten erhalten), kann das Problem durch Messen der -Distanzen gelöst werden , wobei keine Entartungen (keine Teilmenge von) angenommen werden Punkte sind koplanar). $\mathbb{R}^d$ $O((d+1)n)$ $d+1$

Wählen Sie insbesondere Punkte zufällig aus. Dies sind Ankerpunkte. Aufgrund ihrer paarweisen Abstände können Sie Koordinaten für sie berechnen, die mit ihren paarweisen Abständen übereinstimmen. Berechnen Sie nun für jeden zweiten Punkt den Abstand von zu jedem der Ankerpunkte. Mithilfe der Triangulation und dieser Abstände können Sie die Position von relativ zu den Ankerpunkten und damit die Koordinaten für berechnen . Tun Sie dies für jeden Nicht-Ankerpunkt $d+1$ $P$ $P$ $P$ $P$ $P$ . Jetzt haben Sie Koordinaten für jeden Punkt und können diese Koordinaten verwenden, um den Mittelpunkt zu finden, ohne das Orakel zu bitten, Ihnen weitere paarweise Abstände zu geben. Ich weiß nicht, ob dieser letzte Schritt schneller als die -Zeit ausgeführt werden kann , aber ohne weitere paarweise Abstände. $O(n^2)$

DW
quelle

n

$n$

n - 1

$n-1$

Θ (n^{2})

$\Theta(n^2)$

n

$n$

@ DW Danke - könnten wir im Durchschnitt etwas besseres machen? Dies ist auf ein reales Problem zurückzuführen, sodass die Daten wahrscheinlich „durchschnittlich“ sind (was auch immer das bedeuten mag).

Open Door Logistics

@all - Entschuldigung für die Verwirrung bezüglich der Metrik (ich bin ein Laie in der theoretischen CS). Meine Distanzfunktion entspricht definitiv den 4 Kriterien für einen metrischen Raum gemäß der Wikipedia-Definition eines metrischen Raum- Links .

Open Door Logistics

@OpenDoorLogistics, ich habe einen Sonderfall hinzugefügt, in dem es möglich erscheint, es besser zu machen.

Schauen Sie sich Piotr Indyks Arbeit an schnellen Algorithmen für metrische Räume an. ( Sublineare Algorithmen für metrische Raumprobleme , in Proceedings of STOC '99 , S. 428–434. ACM, 1999; PS ) Abschnitt 3 enthält einen linearen zeitlichen ungefähren 1-Median-Algorithmus.

user71641
quelle

Können Sie eine Zusammenfassung des Algorithmus geben? Wir suchen idealerweise nach vollständigen Antworten und nicht nach Links zu externen Inhalten.

David Richerby

Entschuldigung für die sehr langsame Antwort. Ich überprüfe StackExchange offensichtlich nicht sehr oft. Ich denke, ich würde mehr als eine Stunde brauchen, um eine halbwegs anständige Zusammenfassung zu schreiben, während Piotrs Artikel wunderschön geschrieben ist, den Algorithmus sehr klar erklärt und alle genauen Definitionen daneben enthält. Daher würde ich persönlich dringend empfehlen, diesen hochwertigen externen Inhalt anstelle des von mir produzierten internen Inhalts mittlerer Qualität zu verwenden. Die kurze Antwort lautet: Wenn Sie bereit sind, nur einen ungefähren Median zu finden, können Sie dies in der linearen Zeit O (n) tun .

user71641