Podręcznik Grafika komputerowa i wizualizacja

Istnieje bardzo wiele problemów, z którymi spotykamy się w codziennym życiu nie zdając sobie sprawy z tego, że są to typowe problemy geometrii obliczeniowej. Co więcej, problemy te są znane od setek lat, a ich rozwiązanie spędzało sen z powiek wielu matematykom. Niektóre z tych zadań są na tyle trudne, że prace nad ich rozwiązaniem trwają dalej. Dla innych udowodniono, że nie istnieją proste i efektywne rozwiązania. Jest również grupa zadań, dla których opracowano skuteczne i efektywne algorytmy postępowania, co pozwoliło przyspieszyć prace nad rozwiązaniami stosowanymi potem powszechnie w naszym życiu. Telefonia komórkowa jest jednym z przykładów powszechnie wykorzystywanej techniki, która nie mogłaby być stosowana bez odpowiedniego rozwiązania problemów geometrii obliczeniowej.

Problem ochrony galerii (problem muzealny)

Wyobraźmy sobie galerię obrazów zajmującą wiele połączonych ze sobą sal (rys. 3.1). Każdy obraz jest cenny, każdy wymaga uwagi personelu, który musi zadbać o to, aby nikt nie uszkodził ani nie ukradł zbiorów galerii. Powstaje pytanie: ile co najmniej osób musi pilnować zbiorów galerii. Oczywiście zamiast strażników można wykorzystać odpowiednie czujniki lub kamery. .Przyjmuje się, że jeden punktowy czujnik (kamera lub osoba) może „obserwować” (a tym samym chronić) przestrzeń wokół siebie spełniając następujące założenie:

• jest nieruchomy,
• obserwuje w kącie pełnym (2p) przestrzeń wokół siebie,
• może obserwować obiekty z dowolnego dystansu (odległość nie jest istotna),
• nie widzi przez ściany (ściany są nieprzezroczyste).

Rys.3.1. Problem ochrony galerii.Rysunek pochodzi z wikipedii (CC BY).

Tak sformułowany problem nosi w literaturze nazwę art gallery problem. Istnieje twierdzenie V.Chvátala (tzw. twierdzenie o galerii sztuki lub twierdzenie o wartownikach), że jeśli sale galerii są ograniczone n ścianami to minimalna liczba strażników wynosi floor(n/3). Gdzie floor(x) oznacza największą liczbę całkowitą mniejszą lub równą x. Twierdzenie to zostało udowodnione w1975 roku.

Niech danych będzie n węzłów na płaszczyźnie. Należy podzielić płaszczyznę na n wielokątów wypukłych (rys. 3.2) w taki sposób, aby spełnione były następujące warunki:

• w każdym wielokącie znajduje się dokładnie jeden węzeł,
• odległość dowolnego punktu wielokąta od węzła danego wielokąta  jest mniejsza nić odległość od innego węzła.

 Tak sformułowane zadanie rozpatrywał w  1644 roku René Descartes, a później J.Dirichlet w 1850 roku. Nazwa problemu pochodzi od nazwiska Gieorgija Woronoja, który w 1907 roku uogólnił zadanie do problemu wielowymiarowego.