Approximating a shortest watchman route

• Autorzy: Nilsson, B.J.
• Języki publikacji: EN

Abstrakty

EN

We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in O(nlogn) time as compared to the best known algorithm that computes a shortest watchman route which runs in O(n6) time.

Słowa kluczowe

EN

computational geometry; art gallery problems; visibility; watchman routes

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 45, nr 3
• Strony: 253-281
• Opis fizyczny: bibliogr. 13 poz.

Twórcy

autor

Nilsson, B.J.

• Department of Technology and Society Malmö University College,