Primárním cílem výzkumu v oblasti kombinatorické výpočetní geometrie je vývoj efektivních algoritmů a datových struktur pro řešení problémů zadaných v termínech základních geometrických objektů: bodů, úseček, mnohoúhelníků, mnohostěnů atd.
Některé z těchto problémů se zdají být tak jednoduché, že až do nástupu počítačů nebyly vůbec považovány za problémy. Vezměme si například problém nejbližší dvojice:
- Dáme-li n bodů v rovině, najděte dva s nejmenší vzájemnou vzdáleností.
Dalo by se spočítat vzdálenosti mezi všemi dvojicemi bodů, kterých je n(n-1)/2, a pak vybrat dvojici s nejmenší vzdáleností. Tento algoritmus hrubé síly trvá O(n2) času; tj. doba jeho provedení je úměrná kvadrátu počtu bodů. Klasickým výsledkem ve výpočetní geometrii byla formulace algoritmu, který trvá O(n log n). Byly také objeveny náhodné algoritmy, které zaberou O(n) očekávaného času, a deterministický algoritmus, který zabere O(n log log n) času.
Třídy problémůUpravit
Základní problémy ve výpočetní geometrii lze klasifikovat různými způsoby podle různých kritérií. Lze rozlišit následující obecné třídy.
Statické problémyEdit
V problémech této kategorie je dán nějaký vstup a je třeba sestrojit nebo najít odpovídající výstup. Mezi základní úlohy tohoto typu patří:
- Konvexní trup:
- Průsečík úseček: Je dána množina bodů, najděte nejmenší konvexní mnohostěn/polygon obsahující všechny body:
- Delaunayova triangulace
- Voronoiův diagram:
- Lineární programování
- Nejbližší dvojice bodů:
- Nejvzdálenější dvojice bodů
- Největší prázdná kružnice:
- Euklidovská nejkratší cesta: Je dána množina bodů, najděte největší kružnici, jejíž střed je uvnitř jejich konvexního pláště a která žádný z nich neuzavírá:
- Mnohoúhelníková triangulace: Spojte dva body v euklidovském prostoru (s polyedrickými překážkami) nejkratší cestou:
- Generování sítí
- Booleovské operace na mnohoúhelnících
Výpočetní složitost této třídy problémů se odhaduje podle času a prostoru (paměti počítače) potřebného k vyřešení dané instance problému.
Geometrické dotazovací problémyUpravit
V geometrických dotazovacích problémech, běžně známých jako geometrické vyhledávací problémy, se vstup skládá ze dvou částí: části vyhledávacího prostoru a části dotazu, která se mění v instancích problému. Vyhledávací prostor je obvykle třeba předem zpracovat tak, aby bylo možné efektivně odpovědět na více dotazů.
Některé základní geometrické dotazovací problémy jsou:
- Vyhledávání v rozsahu: Předběžné zpracování množiny bodů, aby bylo možné efektivně spočítat počet bodů uvnitř oblasti dotazu.
- Lokalizace bodů:
- Nejbližší soused: Při daném rozdělení prostoru na buňky vytvořte datovou strukturu, která efektivně řekne, ve které buňce se nachází bod dotazu:
- Sledování paprsků: Předzpracujte množinu bodů, abyste efektivně zjistili, který bod je nejblíže dotazovanému bodu:
Pokud je prohledávaný prostor fixní, výpočetní složitost pro tuto třídu problémů se obvykle odhaduje pomocí:
- času a prostoru potřebného ke konstrukci datové struktury, ve které se má hledat
- času (a někdy navíc prostoru) pro zodpovězení dotazů.
Pro případ, kdy se prohledávací prostor může měnit, viz „Dynamické problémy“.
Dynamické problémyEdit
Další významnou třídou jsou dynamické problémy, v nichž je cílem najít efektivní algoritmus pro opakované nalezení řešení po každé inkrementální modifikaci vstupních dat (přidání nebo odstranění vstupních geometrických prvků). Algoritmy pro problémy tohoto typu obvykle zahrnují dynamické datové struktury. Kterýkoli z výpočetních geometrických problémů lze převést na dynamický, ovšem za cenu prodloužení doby zpracování. Například problém vyhledávání v rozsahu lze převést na dynamický problém vyhledávání v rozsahu tím, že se zajistí přidávání a/nebo odstraňování bodů. Dynamický problém konvexního trupu spočívá ve sledování konvexního trupu, např. pro dynamicky se měnící množinu bodů, tj, zatímco vstupní body jsou vkládány nebo odstraňovány.
Výpočetní složitost pro tuto třídu problémů se odhaduje pomocí:
- času a prostoru potřebného ke konstrukci datové struktury, v níž se má hledat
- času a prostoru pro úpravu prohledávané datové struktury po inkrementální změně v prohledávaném prostoru
- času (a někdy navíc prostoru) pro zodpovězení dotazu.
VariantyEdit
Některé problémy lze v závislosti na kontextu považovat za patřící do kterékoli z těchto kategorií. Uvažujme například následující problém:
- Bod v mnohoúhelníku:
V mnoha aplikacích se tento problém považuje za jednorázový, tj. patřící do první třídy. Například v mnoha aplikacích počítačové grafiky je běžným problémem zjistit, na kterou oblast na obrazovce klikne ukazatel. V některých aplikacích je však daný polygon neměnný, zatímco bod představuje dotaz. Například vstupní polygon může představovat hranici země a bod je poloha letadla a problémem je určit, zda letadlo hranici porušilo. Konečně v již zmíněném příkladu počítačové grafiky jsou v aplikacích CAD měnící se vstupní data často uložena v dynamických datových strukturách, čehož lze využít ke zrychlení dotazů typu bod v polygonu.
V některých kontextech dotazovacích problémů existují rozumná očekávání ohledně posloupnosti dotazů, což lze využít buď pro efektivní datové struktury, nebo pro přísnější odhady výpočetní složitosti. V některých případech je například důležité znát nejhorší případ celkového času pro celou posloupnost N dotazů, nikoli pro jeden dotaz. Viz také „amortizovaná analýza“.