Podstawowym celem badań w kombinatorycznej geometrii obliczeniowej jest opracowanie wydajnych algorytmów i struktur danych do rozwiązywania problemów podanych w kategoriach podstawowych obiektów geometrycznych: punktów, odcinków linii, wielokątów, wielościanów itp.
Niektóre z tych problemów wydają się tak proste, że do czasu pojawienia się komputerów nie były w ogóle uważane za problemy. Rozważmy, na przykład, problem najbliższej pary:
- Dając n punktów na płaszczyźnie, znajdź dwa z najmniejszą odległością od siebie.
Można obliczyć odległości między wszystkimi parami punktów, których jest n(n-1)/2, a następnie wybrać parę z najmniejszą odległością. Ten algorytm brute-force zajmuje O(n2) czasu; tzn. jego czas wykonania jest proporcjonalny do kwadratu liczby punktów. Klasycznym wynikiem w geometrii obliczeniowej było sformułowanie algorytmu, który zajmuje O(n log n). Odkryto również algorytmy randomizowane, które zajmują O(n) czasu oczekiwanego, a także algorytm deterministyczny, który zajmuje O(n log log n) czasu.
Klasy problemówEdit
Główne problemy geometrii obliczeniowej mogą być klasyfikowane w różny sposób, według różnych kryteriów. Można wyróżnić następujące klasy ogólne.
Problemy statyczneEdit
W problemach tej kategorii dane są pewne dane wejściowe, a odpowiadające im dane wyjściowe muszą być skonstruowane lub znalezione. Niektóre podstawowe problemy tego typu to:
- Kadłub wypukły: Given a set of points, find the smallest convex polyhedron/polygon containing all the points.
- Line segment intersection: Znajdź przecięcia między danym zbiorem odcinków linii.
- Triangulacja Delaunay’a
- Diagram Voronoi: Given a set of points, partition the space according to which points are closest to the given points.
- Programowanie liniowe
- Najbliższa para punktów: Biorąc pod uwagę zbiór punktów, znajdź dwa o najmniejszej odległości od siebie.
- Najdalsza para punktów
- Największy pusty okrąg: Given a set of points, find a largest circle with its center inside of their convex hull and enclosing none of them.
- Euclidean shortest path: Połącz dwa punkty w przestrzeni euklidesowej (z przeszkodami wielościanowymi) najkrótszą ścieżką.
- Triangulacja wielokąta: Given a polygon, partition its interior into triangles
- Mesh generation
- Boolean operations on polygons
Złożoność obliczeniowa dla tej klasy problemów jest szacowana przez czas i przestrzeń (pamięć komputera) wymagane do rozwiązania danej instancji problemu.
Geometryczne problemy zapytańEdit
W geometrycznych problemach zapytań, powszechnie znanych jako geometryczne problemy wyszukiwania, dane wejściowe składają się z dwóch części: części przestrzeni wyszukiwania i części zapytania, która jest różna w różnych instancjach problemu. Przestrzeń przeszukiwania zazwyczaj musi być wstępnie przetworzona w taki sposób, aby można było efektywnie odpowiedzieć na wiele zapytań.
Niektóre podstawowe problemy geometryczne to:
- Przeszukiwanie zakresu: Wstępne przetworzenie zbioru punktów, w celu efektywnego policzenia liczby punktów wewnątrz regionu zapytania.
- Lokalizacja punktów: Given a partitioning of the space into cells, produce a data structure that efficiently tells in which cell a query point is located.
- Nearest neighbor: Wstępne przetwarzanie zbioru punktów, w celu efektywnego znalezienia, który punkt jest najbliżej punktu zapytania.
- Śledzenie promieni: Biorąc pod uwagę zbiór obiektów w przestrzeni, wyprodukuj strukturę danych, która wydajnie mówi, który obiekt promień zapytania przecina jako pierwszy.
Jeśli przestrzeń wyszukiwania jest stała, złożoność obliczeniowa dla tej klasy problemów jest zwykle szacowana przez:
- czas i przestrzeń wymaganą do skonstruowania struktury danych, w której ma być przeszukiwana
- czas (i czasami dodatkową przestrzeń) na odpowiedzi na zapytania.
Dla przypadku, gdy przestrzeń przeszukiwania może się zmieniać, patrz „Problemy dynamiczne”.
Problemy dynamiczneEdit
Jeszcze inną ważną klasą są problemy dynamiczne, w których celem jest znalezienie efektywnego algorytmu znajdowania rozwiązania wielokrotnie po każdej inkrementalnej modyfikacji danych wejściowych (dodanie lub usunięcie wejściowych elementów geometrycznych). Algorytmy dla tego typu problemów zazwyczaj wykorzystują dynamiczne struktury danych. Każdy z obliczeniowych problemów geometrycznych może być przekształcony w problem dynamiczny, kosztem zwiększenia czasu przetwarzania. Na przykład, problem przeszukiwania zakresu może być przekształcony w dynamiczny problem przeszukiwania zakresu poprzez zapewnienie dodawania i/lub usuwania punktów. Problem dynamicznego kadłuba wypukłego polega na śledzeniu kadłuba wypukłego, np. dla dynamicznie zmieniającego się zbioru punktów, tj, podczas gdy punkty wejściowe są wstawiane lub usuwane.
Złożoność obliczeniowa dla tej klasy problemów jest szacowana przez:
- czas i przestrzeń wymagane do skonstruowania struktury danych, która ma być przeszukiwana w
- czas i przestrzeń do modyfikacji przeszukiwanej struktury danych po przyrostowej zmianie w przestrzeni przeszukiwania
- czas (i czasami dodatkową przestrzeń) do odpowiedzi na zapytanie.
WariacjeEdit
Niektóre problemy mogą być traktowane jako należące do którejś z kategorii, w zależności od kontekstu. Na przykład, rozważ następujący problem.
- Punkt w wielokącie: Rozstrzygnij, czy punkt jest wewnątrz czy na zewnątrz danego wielokąta.
W wielu zastosowaniach problem ten jest traktowany jako jednostrzałowy, tzn. należący do klasy pierwszej. Na przykład w wielu zastosowaniach grafiki komputerowej częstym problemem jest znalezienie, który obszar na ekranie jest kliknięty przez wskaźnik. Jednak w niektórych zastosowaniach, dany wielokąt jest niezmienny, natomiast punkt reprezentuje zapytanie. Na przykład, wielokąt wejściowy może reprezentować granicę państwa, a punkt jest pozycją samolotu, a problem polega na określeniu, czy samolot naruszył granicę. Wreszcie, we wspomnianym wcześniej przykładzie grafiki komputerowej, w aplikacjach CAD zmieniające się dane wejściowe są często przechowywane w dynamicznych strukturach danych, które mogą być wykorzystane do przyspieszenia zapytań typu punkt-w-poligonie.
W niektórych kontekstach problemów z zapytaniami istnieją uzasadnione oczekiwania co do kolejności zapytań, które mogą być wykorzystane albo do wydajnych struktur danych, albo do ściślejszego oszacowania złożoności obliczeniowej. Na przykład, w niektórych przypadkach ważne jest, aby znać najgorszy przypadek dla całkowitego czasu dla całej sekwencji N zapytań, a nie dla pojedynczego zapytania. Zobacz także „analiza amortyzowana”.