Granice kompromisowe dla liczenia zakresu półprzestrzeni

10

Jaki jest obecnie najlepszy sposób wykonywania zapytań zliczających zakres półprzestrzeni na zbiorze punktów wymiarowych, wyrażony w formie kompromisu czas / przestrzeń. Zgodnie z przełomowym referatem Matouseka z 1993 r. (Twierdzenie 6.2, Wyszukiwanie zasięgu za pomocą wydajnych wycinków hierarchicznych), możemy wykonać zliczanie zasięgu dla zapytań, które są przecięciem półprzestrzeni , dla , przy użyciu struktury danych o rozmiarze , dla , w czas. Dla jest to czas . Jednak badanie Agarwal dotyczące przeszukiwania zasięgu (Tabela 36.3.2) twierdzi, że jest to granica $d$ $p$ $1 \le p \le d+1$ $O(m)$ $n \le m \le n^d$ $O\left(\frac{n}{m^{1/d}}\log^{p-(d-p+1)/d} \left(\frac{m}{n}\right)\right)$ $p=1$ $O(n/m^{1/d})$ $O\left(\frac{n}{m^{1/d}}\log(\frac{m}{n})\right)$ . Jakie jest prawidłowe oświadczenie związane? Alternatywnie, co ja mylę? Wreszcie, czy istnieje jakiś ukryty termin w dzienniku, gdy ? $m=n^d$

reference-request ds.data-structures cg.comp-geom

— pkn
źródło

6

Mocniejszy termin Matouška jest prawidłowy.

Dowód Twierdzenia 6.1 ( w wersji czasopisma ) wykorzystuje sztuczkę pośrednią, która zmniejsza przestrzeń wymaganą dla logarytmicznego czasu zapytania z do . Intuicyjnie sztuczka polega na zgrupowaniu punktów w podzbiory wielkości polilogarytmicznej, zbudowaniu struktury danych w przestrzeni liniowej dla każdego podzbioru, a następnie zbudowaniu standardowej struktury logarytmiczno-czasowo-kwerendowej na podzestawach. Podłączanie ulepszonej przestrzeni związanej z wielopoziomową / kompromisową maszyną Matouška - opisaną krwawą ogólnością w dłuższej wersji ankiety Agarwal $O(n^d)$ $O(n^d/\operatorname{polylog} n)$ —Daje kompromisowi Matouška w czasoprzestrzeni. (W rzeczywistości sztuczka pośrednia to po prostu bardzo staranne zastosowanie standardowego mechanizmu wymiany).

— Jeffε
źródło

Mówiąc wprost: Twierdzenie 6.2 w pracy Matouseka twierdzi, że zliczanie półprzestrzeni można wykonać w przestrzeni

, czasie

. Gdy

, to jest czas

... nie ma nieokreślonego addytywnego współczynnika logarytmicznego? Pytam tylko dlatego, że w badaniu Twierdzenie 7 i Wniosek 8 mają dodatek

który nie jest obecny w twierdzeniu Matouseka.

O (m)

$O(m)$

O (n / m^{1 / d})

$O(n/m^{1/d})$

m = n^{d}

$m = n^d$

O (1)

$O(1)$

O (l o g (m / n))

$O(log (m/n))$

— pkn

O, rozumiem. Tak, jest błąd; górna granica

w twierdzeniu twierdzenia jest zbyt luźna. Dowód wymaga

; w przeciwnym razie parametr liczby całkowitej

byłby mniejszy niż

. Dodanie terminu logairthmic do czasu zapytania również rozwiązuje problem.

m \leq n^{d}

$m \le n^d$

m = O (n^{d} / \log^{d - p + 1} n)

$m = O(n^d / \log^{d-p+1} n)$

r

$r$

1

$1$

— Jeffε

2

Krótkie omówienie wyników w zakresie przeszukiwania półprzestrzeni znajduje się tuż nad tabelą 36.3.2 w badaniu Agarwala , a inne w sekcji 4.3 tego badania . Pierwszy z nich nie wydaje się podawać wielu szczegółów poza „Kompromisem między czasem a zapytaniem dla wyszukiwania zakresu simpleks można uzyskać przez połączenie struktur danych o wielkości liniowej i logarytmicznych w czasie zapytania”, ale ten drugi wydaje się zapewniać całkiem sporo więcej szczegółów na temat kompromisu przestrzeń / czas zapytania. Proponuję spojrzeć na rozdział 4.3, Twierdzenie 7, Wniosek 8 i ich dowody. Nie przeczytałem ich wystarczająco szczegółowo, aby wiedzieć, czy w pełni odpowiada na twoje pytanie, ale to przynajmniej dobre miejsce, aby zacząć.

— Joe
źródło