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.

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) \}$$ $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{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)$ leży na kole $C(a,b,c)$ wtedy i tylko wtedy gdy $$\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\times4$ wyznacznik do następującej postaci: $$(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0 \tag{$*$}$$ A zatem, $(t,t^2)$ leży na $C(a,b,c)$ wtedy i tylko wtedy gdy $t=a$, $t=b$, $t=c$lub $t=-a-b-c < 0$. Ponadto, ponieważ$0<a<b<c$, te cztery korzenie są odrębne, co oznacza, że ​​parabola faktycznie przecina się $C(a,b,c)$w tych czterech punktach. Wynika, że$(t,t^2)$leży w środku $C(a,b,c)$ wtedy i tylko wtedy gdy $-a-b-c<t<a$ lub $b<t<c$.$\qquad\Box$