Wdrożenie drzew partycji?

11

Czy kiedykolwiek zaimplementowano drzewa partycji?

Mówię tutaj o drzewach partycji z geometrii obliczeniowej. Najwcześniejsze (prawie) optymalne wersje były spowodowane przez Matouseka i innych, a ostatnio Timothy Chan:

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

To dla mnie szaleństwo, że nigdy nie zostały zaimplementowane, ale Google nie wykrył żadnych implementacji, o których nikt wcześniej nie donosił.

ds.data-structures implementation computational-geometry Pat Morin
źródło
Skąd ten cytat? Mój czytnik PDF nie znajduje go w dokumencie T. Chan, do którego prowadzi link.
jbapple,
Pochodzi z manuskryptu, a nie z gazety Chana. Chcę to zweryfikować tak dokładnie, jak to możliwe, zanim zostanie opublikowany.
Pat Morin
6
Nie znam kontekstu tego pytania, ale: (1) Jeśli recenzujesz manuskrypt, nie sądzę, aby udostępnianie części recenzowanego manuskrytu w ten sposób było takie. (2) Artykuł nie powinien zawierać takiego twierdzenia, ponieważ nawet jeśli jest to prawda, nie można go zweryfikować. Na przykład nikt nie może wykluczyć, że ktoś wdrożył go jako projekt osobisty i nigdy nie zadał sobie trudu, aby udostępnić go publicznie.
Tsuyoshi Ito
1
Dziękuję za pomocną radę. To rękopis pracy napisanej przez mojego studenta. Prawdopodobnie sformułowałbym inaczej: ponieważ mimo dokładnych poszukiwań nie jesteśmy świadomi żadnych implementacji drzew partycji. (Dokładnie szukam, co teraz robię, częściowo z tym pytaniem.)
Pat Morin
2
Czy możesz uprościć pytanie, usuwając cytat z rękopisu? Obecnie twój post zawiera dwa pytania (z których żadne nie jest wyraźnie określone): (1) Jak mam sprawdzić prawdziwość twierdzenia, że ​​drzewa partycji nigdy nie zostały zaimplementowane? Odpowiedź: Nie powinieneś. (2) Czy ludzie znają jakieś implementacje drzew partycji? Nie znam odpowiedzi na tę część, ale myślę, że pytanie jest w porządku. Jedynym problemem związanym z (2) jest to, że nikt nie może powiedzieć „nie” na to pytanie, ale możesz wywnioskować to po pewnym czasie, jeśli nikt nie wymyśli implementacji.
Tsuyoshi Ito

Odpowiedzi:

3

Zgodnie z definicją w powiązanym dokumencie na stronie 5 stwierdzenie jest błędne. Binarny podział przestrzeni (BSP) drzewa zostały wykorzystane przez dziesięciolecia na grafice komputerowej w celu przyspieszenia zapytań przestrzennych, jak mają quadtrees i octrees . Drzewa Kd są szeroko stosowane w uczeniu maszynowym, aby przyspieszyć wyszukiwanie najbliższych sąsiadów. Jeśli trochę się zmrużysz, drzewa decyzyjne pasują również do ogólnej definicji.

Neil Toronto
źródło
2
Tak, byłem tego świadomy. Nie znalazłem jednak żadnej implementacji drzewa BSP dla zestawów punktów, która wykonuje dowolne fantazyjne czynności wymagane, aby utrzymać liczbę przebijania blisko O (sqrt (n)).
Pat Morin
3
To nie są drzewa partycji w tym sensie, że zadaje to pytanie. Myślę, że OP szuka struktur danych do przeszukiwania półprzestrzeni.
Mikola