Jaki jest najgorszy przypadek losowego algorytmu triangulacji przyrostowej delauny?

Wiem, że oczekiwany najgorszy czas działania randomizowanego przyrostowego algorytmu triangulacji delauny (jak podano w geometrii obliczeniowej ) to . Istnieje ćwiczenie sugerujące, że najgorszym środowiskiem uruchomieniowym jest . Próbowałem skonstruować przykład, w którym tak naprawdę jest, ale jak dotąd nie udało się. $\mathcal O(n \log n)$ $\Omega(n^2)$

Jeden z tych prób było przygotowanie i obciążenie wartości zadanej w taki sposób, że podczas dodawania punktu w etapie , o krawędzie są utworzone. $p_r$ $r$ $r-1$

Inne podejście może obejmować strukturę punkt-lokalizacja: Spróbuj ułożyć punkty tak, aby ścieżka w strukturze punkt-lokalizacja w celu zlokalizowania punktu w kroku była jak najdłuższa. $p_r$ $r$

Mimo to nie jestem pewien, które z tych dwóch podejść jest poprawne (jeśli w ogóle) i chętnie skorzystam z kilku wskazówek.

— Tedil
źródło

Spróbuj umieścić wszystkie punkty na krzywej dla niektórych dobrze wybranych .

y = x^{r}

$y = x^r$

r

$r$

— Peter Shor,

Pierwsze podejście można sformalizować w następujący sposób.

Niech będzie dowolnym zbiorem punktów na dodatniej gałęzi paraboli ; to znaczy, dla niektórych dodatnich liczb rzeczywistych . Bez utraty ogólności załóżmy, że punkty te są indeksowane w kolejności rosnącej: . $P$ $n$ $y=x^2$

P = {(t_{1}, t_{1}^{2}), (t_{2}, t_{2}^{2}), \dots, (t_{n}, t_{n}^{2})}

$P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \}$

t_{1}, t_{2}, \dots, t_{n}

$t_1, t_2, \dots, t_n$

0 < t_{1} < t_{2} < \dots < t_{n}

$0 < t_1 < t_2 < \cdots < t_n$

Twierdzenie: W triangulacji Delaunaya z $P$ , skrajnie lewy punkt $(t_1, t_1^2)$ jest sąsiadem każdego innego punktu w $P$ .

Twierdzenie to oznacza, że dodanie nowego punktu $(t_0, t_0^2)$ do $P$ z $0 < t_0 < t_1$ dodaje $n$ nowe krawędzie triangulacji Delaunaya. Zatem indukcyjnie, jeśli stopniowo narastamy triangulację Delaunaya $P$ wstawiając punkty w kolejności od prawej do lewej , całkowita liczba utworzonych krawędzi Delaunay wynosi $\Omega(n^2)$ .

Możemy udowodnić roszczenie w następujący sposób. Dla dowolnych rzeczywistych wartości $0<a<b<c$ , pozwolić $C(a,b,c)$ oznacz unikalny okrąg przez punkty $(a,a^2), (b,b^2), (c,c^2)$ .

Lemat: $C(a,b,c)$ nie zawiera żadnego punktu $(t,t^2)$ gdzie $a<t<b$ lub $c<t$ .

Dowód: Przypomnij sobie cztery punkty $(a,b), (c,d), (e,f), (g,h)$ są okrągłe, jeśli i tylko wtedy, gdy

| \begin{matrix} 1 & a & b & a^{2} + b^{2} \\ 1 & c & d & c^{2} + d^{2} \\ 1 & e & f & e^{2} + f^{2} \\ 1 & g & h & g^{2} + h^{2} \end{matrix} | = 0

$\begin{vmatrix} 1 & a & b & a^2 + b^2 \\ 1 & c & d & c^2 + d^2 \\ 1 & e & f & e^2 + f^2 \\ 1 & g & h & g^2 + h^2 \\ \end{vmatrix} = 0$ Tak więc punkt

(t, t^{2})

$(t,t^2)$ leży na kole

C (a, b, c)

$C(a,b,c)$ wtedy i tylko wtedy gdy

| \begin{matrix} 1 & a & a^{2} & a^{2} + a^{4} \\ 1 & b & b^{2} & b^{2} + b^{4} \\ 1 & c & c^{2} & c^{2} + c^{4} \\ 1 & t & t^{2} & t^{2} + t^{4} \end{matrix} | = 0

$\begin{vmatrix} 1 & a & a^2 & a^2 + a^4 \\ 1 & b & b^2 & b^2 + b^4 \\ 1 & c & c^2 & c^2 + c^4 \\ 1 & t & t^2 & t^2 + t^4 \\ \end{vmatrix} = 0$ To nie jest trudne (na przykład zapytaj Wolfram Alpha), aby rozwinąć i uwzględnić

4 \times 4

$4\times4$ wyznacznik do następującej postaci:

\begin{matrix} (*) & (a - b) (a - c) (b - c) (a - t) (b - t) (c - t) (a + b + c + t) = 0 \end{matrix}

$(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0 \tag{$*$}$ A zatem,

(t, t^{2})

$(t,t^2)$ leży na

C (a, b, c)

$C(a,b,c)$ wtedy i tylko wtedy gdy

t = a

$t=a$ ,

t = b

$t=b$ ,

t = c

$t=c$ lub

t = - a - b - c < 0

$t=-a-b-c < 0$ . Ponadto, ponieważ

0 < a < b < c

$0<a<b<c$ , te cztery korzenie są odrębne, co oznacza, że parabola faktycznie przecina się

C (a, b, c)

$C(a,b,c)$ w tych czterech punktach. Wynika, że

(t, t^{2})

$(t,t^2)$ leży w środku

C (a, b, c)

$C(a,b,c)$ wtedy i tylko wtedy gdy

- a - b - c < t < a

$-a-b-c<t<a$ lub

b < t < c

$b<t<c$ .

◻

$\qquad\Box$

— Jeffε
źródło

Dziękuję, chociaż tak naprawdę chciałem tylko podpowiedzi (bez dowodu);)

— Tedil