Wyznaczanie Euklidesowej najkrótszej drogi na płaszczyźnie pomiędzy dwoma punktami z pominięciem wielokątnych przeszkód.

Speaker(s)

Anna Wojak

Affiliation

Uniwersytet Warszawski

Date

Jan. 26, 2006, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Wyznaczanie Euklidesowej najkrótszej ścieżki jest jednym z najstarszych i dobrze znanych problemów w geometrii obliczeniowej. Obecnie istnieje wiele typów problemów związanych z wyznaczaniem najkrótszych dróg. Rozważmy płaszczyznę zawierająca zbiór rozłącznych przeszkód, których liczba wierzchołków wynosi n oraz dany punkt źródła s. Problemem jest wyznaczenie najkrótszej drogi z punktu s do wszystkich punktów wolnej przestrzeni. Znane są dwie główne metody wyznaczania najkrótszych ścieżek: visibility graph (VG) oraz shortest path map (SPM) połączone z algorytmami Dijkstra oraz A*. Shortest path map polega na specjalnym podziale płaszczyzny na obszary ukorzenione w wierzchołkach przeszkód. Obszary te są wyznaczane za pomocą rozchodzenia się czoła fali frontowej z punktu źródła s na całą płaszczyznę pośród wielokątnych przeszkód. Na początku lat dziewięćdziesiątych J.S.B. Mitchell pokazał, że wyznaczenie SPM wymaga O(n^{3/2} + \epsilon) dla \epsilon > 0. Następnie Jonh Hersberger oraz Subhash Suri zaproponowali optymalny algorytm dla SPM działający w najgorszym przypadku w czasie O(nlogn) i wymagający O(nlogn) pamięci. Kluczowym pomysłem ich algorytmu jest specjalny podział płaszczyzny zwany conforming subdividion, który może być wyznaczony w czasie O(n+nlogn).

---