Pytania oznaczone «delaunay-triangulation»

Czy triangulacje Delaunaya na sferze maksymalizują minimalny kąt?

Triangulacje Delaunaya w płaszczyźnie maksymalizują minimalny kąt w trójkącie. Czy to samo dotyczy triangulacji punktów w kuli ziemskiej przez Delaunaya? (tutaj „kąt” to kąt lokalny w sąsiedztwie wierzchołka na wierzchołku). Zainspirowany, ale niezwiązany z tym pytaniem na...

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...