Implementierung von Partitionsbäumen?

11

Wurden jemals Partitionsbäume implementiert?

Hier spreche ich über die Partitionsbäume aus der Rechengeometrie. Die frühesten (nahezu) optimalen Versionen davon waren Matousek und anderen zu verdanken, und zuletzt Timothy Chan:

https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf

Es klingt verrückt für mich, dass diese nie implementiert wurden, aber beim Googeln wurden keine Implementierungen gefunden, über die jemals jemand berichtet hat.

ds.data-structures implementation computational-geometry Pat Morin
quelle
Woher kommt das Zitat? Mein PDF-Reader findet es nicht in dem von Ihnen verlinkten T. Chan-Papier.
jbapple
Es ist aus einem Manuskript, nicht aus Chans Papier. Ich möchte dies nur so gründlich wie möglich überprüfen, bevor es veröffentlicht wird.
Pat Morin
6
Ich kenne den Kontext dieser Frage nicht, aber: (1) Wenn Sie ein Manuskript überprüfen, halte ich es nicht für in Ordnung, einen Teil des zu überprüfenden Manuskripts so zu teilen. (2) Ein Papier sollte einen solchen Anspruch nicht erheben, da er selbst dann nicht überprüfbar ist, wenn er wahr ist. Zum Beispiel kann niemand die Möglichkeit ausschließen, dass jemand sie als persönliches Projekt implementiert hat und sich nie die Mühe gemacht hat, es öffentlich zu teilen.
Tsuyoshi Ito
1
Danke für den hilfreichen Rat. Es ist ein Manuskript einer von meinem Studenten verfassten Arbeit. Ich würde wahrscheinlich umformulieren als: Trotz gründlicher Suche sind uns keine Implementierungen von Partitionsbäumen bekannt. (Gründliche Suche ist das, was ich jetzt mache, teilweise mit dieser Frage.)
Pat Morin
2
Könnten Sie die Frage vereinfachen, indem Sie das Zitat aus dem Manuskript entfernen? Derzeit enthält Ihr Beitrag zwei Fragen (von denen keine explizit angegeben ist): (1) Wie sollte ich die Richtigkeit der Behauptung überprüfen, dass Partitionsbäume nie implementiert wurden? Antwort: Das solltest du nicht. (2) Kennen Leute Implementierungen von Partitionsbäumen? Ich kenne die Antwort auf diesen Teil nicht, aber ich denke, dass es als Frage in Ordnung ist. Das einzige Problem mit (2) ist, dass niemand zu dieser Frage „Nein“ sagen kann, aber Sie können daraus nach einiger Zeit schließen, wenn niemand eine Implementierung findet.
Tsuyoshi Ito

Antworten:

3

Nach der Definition im verlinkten Papier auf Seite 5 ist die Aussage falsch. BSP-Bäume (Binary Space Partition) werden seit Jahrzehnten in der Computergrafik verwendet, um räumliche Abfragen zu beschleunigen, ebenso wie Quadtrees und Octrees . Kd-Bäume werden beim maschinellen Lernen häufig verwendet, um die Suche nach nächsten Nachbarn zu beschleunigen. Wenn Sie nur ein wenig blinzeln, passen Entscheidungsbäume auch zur allgemeinen Definition.

Neil Toronto
quelle
2
Ja, das war mir bewusst. Was ich jedoch nicht gefunden habe, ist eine Implementierung eines BSP-Baums für Punktmengen, der alle ausgefallenen Dinge erledigt, die erforderlich sind, um auch seine Stichzahl nahe bei O (sqrt (n)) zu halten.
Pat Morin
3
Dies sind keine Partitionsbäume in dem Sinne, wie es die Frage stellt. Ich denke, das OP sucht speziell nach Datenstrukturen für die Suche im halben Raumbereich.
Mikola