Algoritmická geometrie

Výpočetní geometrie je pole algoritmické , která se zabývá algoritmy manipulaci s pojmy geometrické .

Definice a první příklady

Algoritmická geometrie je studium algoritmů manipulujících s geometrickými objekty . Například algoritmický problém, který spočívá v nalezení dvojice bodů v rovině popsané jejich souřadnicemi, při hledání dvojice bodů, jejichž vzdálenost je minimální, je problém geometrických algoritmů.

Historie a použití

Jedním z počátků této disciplíny je skutečnost, že počítačové modely, tedy virtuální realita, nahrazují modely v designu objektů od 70. let 20. století. Tyto modely pak umožňují studium nejrůznějších jevů v reálném světě. Disciplína, která nepochybně nejvíce historicky přispěla k rozvoji výpočetní geometrie, je počítačová grafika . V současné době je však výpočetní geometrie často součástí obecných algoritmických problémů.

Algoritmická geometrie se dnes používá v počítačové grafice, robotice, geografických informačních systémech a počítačovém designu.

Klasická datová struktura

Některé struktury, které lze použít na začátku problému nebo uvnitř algoritmu, jsou v algoritmické geometrii ústřední: mnohostěny , Voronoiovy diagramy a triangulace .

Klasické problémy

Konvexní obálka

Konvexní obálka z množiny bodů na rovině, je nejmenší konvexní polygon obsahující všechny body. Tuto představu lze okamžitě zobecnit na rozměry větší než 2.

Nejlépe známý algoritmus, který v současné době umožňuje určit konvexní obálku libovolné množiny n bodů ve 2D ( Grahamova cesta ) nebo 3D, je v O ( n log ( n )) . Bez dalších znalostí o datech nelze dosáhnout lepších výsledků než Ω ( n log ( n )); existuje však několik O ( n ) algoritmů , které se zabývají případem jednoduchých polygonů (ne-protínajících se polygonů) uvedených v pořadí podle vzhledu bodů. Existují také algoritmy, kde je složitost dána jako funkce počtu bodů n, ale také jako funkce počtu h bodů v konvexní obálce (tj. Výstup algoritmu): Jarvisův chod je algoritmus v O ( nh ) a Chanův algoritmus je v O ( n log h ).

V případě jakékoli dimenze d ( d > 3) jsou nejznámější algoritmy . $\Theta(n^{\lfloor{\frac{d}{2}}\rfloor})$

Obecné algoritmické problémy

Algoritmická geometrie poskytuje optimální řešení problémů popsaných na ohraničeném vesmíru. Ve skutečnosti se tento zabývá problémy uvedenými ve smyslu bodů uspořádaných na ohraničené mřížce [1, X ] × [1, Y ] dimenze 2. Rozšířením se zabývá stejnými problémy na mřížkách vyšších dimenzí a na intervalech celá čísla (dimenze 1).

Například vzhledem k množině bodů S v intervalu celých čísel [1, U ] je možné využít omezeného charakteru vesmíru [1, U ] k vyřešení některých problémů pod jejich složitostí minimální pro neomezený vesmír . Nejtriviálnějším a nejznámějším případem je lineární třídění , kbelík vyjde . Prvky S lze třídit v čase | S | + U prohlížení S jednou a ukládání každý prvek nalezen v „kbelíku“ odpovídající řady korečků pod čísly 1 až U .

Mnoho algoritmických problémů najde optimální řešení v ohraničeném vesmíru:

Vzhledem k množině S mohutnosti n přes celočíselný interval [1, U ],
- Získejte strukturu S nejblíže danému x v čase namísto log ( n ) díky struktuře q-fast-trie . ${\sqrt {\log(U)}}$
Vzhledem k množině S na mřížce [1, U ] x [1, U ].
- Získejte všechny body, které dominují bodu x na jejich dvou souřadnicích v čase k + log (log ( U )), pokud k je počet odpovědí, místo k + log ( n ). Viz také vyhledávání rozsahu ( Range Range ).
Vzhledem k množině I intervalů v intervalu [1, U ],
- Najděte všechny intervaly I, které procházejí daným bodem x v čase k + log (log ( U )) namísto k + log ( n ), pokud k je počet odpovědí, a to díky výzkumu stromové struktury s prioritou.

Některé další důležité otázky

Voronoi diagram a jeho duální graf Delaunay triangulace
Průnik dvou segmentů (in)
Křižovatka dvou linek (in)
Nalezení dvou nejbližších bodů
Triangulace mnohoúhelníku
Problém s uměleckou galerií

Obtíže a techniky

Jednou z potíží je mor dimenze : klasické algoritmy se stanou nepoužitelnými, pokud data patří do velkého prostoru. Klasickou technikou je použití pravděpodobnostních algoritmů .

Poznámky a odkazy

Francis Lazarus, „ Algoritmická geometrie: poznámky k přednášce “ , na Laboratoire GIPSA
Jean-Daniel Boissonnat , „ Algoritmická geometrie: od geometrických dat k datové geometrii “ , Collège de France .