Największa komórka w układzie

P . Jaka jest złożoność znalezienia największej komórki ograniczonej objętością w układzie hiperpłaszczyzn w wymiarze d ?$n$$d$

Wydaje mi się, że powinienem to wiedzieć ... Ale nie znajduję ostatecznego odniesienia.

Czy to ? Co powiesz na specjalizację d = 2 : Największy obszar ograniczony komórką w układzie linii?$\Omega(n^d)$$d{=}2$

Jakoś radzenie sobie lepiej niż wygląda na trudne. Jeśli komórka jest znacznie większa niż jej średnia oczekiwana wielkość, można użyć próbkowania, aby ją znaleźć. Formalnie załóżmy, że ograniczone komórki (w płaszczyźnie) tworzą wielokąt z obszaru 1 (ten wielokąt Q można obliczyć w czasie prawie liniowym w płaszczyźnie). Załóżmy, że największa ograniczona komórka C w układzie linii ma pole α ≫ 1 / n 2 . Próbka, m = ( log n ) / α punktów z Q - i niech $O(n^d)$$1$$Q$$C$$\alpha \gg 1/n^2$$m = (\log n)/\alpha$$Q$$P$ będzie wynikowym zestawem punktów. Z dużym prawdopodobieństwem jeden z punktów wpada do , a obliczenie wszystkich ścian w układzie zawierającym punkty P zajmuje$C$$P$ Czas przy użyciu standardowej magii (tj. algorytmów do obliczania wielu twarzy w układzie linii).$O(( n^{2/3} m^{2/3} + n + m)*\mathrm{polylog})$

To jest łatwe do zastosowania przeszukiwanie binarne w , aby algorytm oblicza największą komórki w czasie O ( ( n + 1 / α + n 2 / 3 / α 2 / 3 ) p O L y l O g N ) , gdzie α jest ułamkiem powierzchni największej komórki z całkowitego obszaru komórek ograniczonych (tj. obszaru Q ).$\alpha$$O\Bigl( \bigl(n + 1/\alpha + n^{2/3}/\alpha^{2/3}\bigr) \mathrm{polylog n}\Bigr)$$\alpha$$Q$