Dynamische planare exakte k-nächste Nachbarn für pathologische Daten

8

Was sind die bekanntesten Ergebnisse für eine Datenstruktur, die die folgenden Operationen für Punktmengen im zweidimensionalen euklidischen Raum bietet:

  • ichnsert(x)
  • delete(x)
  • (wobei k eine ganze Zahl größer als 0 ist) gibt die k Punkte zurück, die x amnächsten liegen,die sich in der Menge befinden.nearest(k,x)kkx

In diesem speziellen Fall bin ich nicht besonders an ungefähren nächsten Nachbarn, Monte-Carlo-Algorithmen oder Algorithmen interessiert, die davon ausgehen, dass die Daten in irgendeiner Weise gut geformt sind.

Ich bin nicht so voreingenommen gegenüber Las Vegas-Algorithmen, Algorithmen, die annehmen, dass die Koordinaten des Punktes -Bits haben, oder Algorithmen mit einer Laufzeit in Abhängigkeit von .O(lgn)k

jbapple
quelle
Ich nehme an, dass Teil der Abfrageeingabe ist und keine feste Konstante ist. k
Suresh Venkat
Sie nehmen richtig an.
jbapple
davor hatte ich Angst. Das Problem ist, dass, da k so viel wie n / 2 sein kann, Sie wirklich nach mittleren Ebenen einer Anordnung von Funktionen fragen und diese sich beim Einfügen und Löschen stark ändern können.
Suresh Venkat
Hilft es, wenn k sowohl Teil der Abfrageeingabe als auch ein Parameter der Laufzeit ist? (Ich denke, dies wird als "ausgabesensitiv" bezeichnet)
jbapple
Es sollte helfen, und das hatte ich mir gedacht. Es ist jedoch unwahrscheinlich, dass Sie einfache Grenzen der Form . f(n)+k
Suresh Venkat

Antworten:

7

Gemäß TOPP 63 können dynamische nächste Nachbarn in Polylog ) pro Einfügen, Löschen oder Abfragen beantwortet werden ( dh der Fall k = 1 ). Der allgemeine Fall kann daher auch in der Zeit O ( k Polylog ) pro Abfrage beantwortet werden: Um eine Abfrage für k Punkte durchzuführen, suchen und löschen Sie wiederholt den nächsten Nachbarn, und fügen Sie nach Abschluss der Abfrage alle gelöschten Punkte erneut ein.Ö()k=1Ö(k)k

David Eppstein
quelle