1
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ę.O(nlogn)O(nlogn)\mathcal O(n \log n)Ω(n2)Ω(n2)\Omega(n^2) Jeden z tych prób było …