Algoritmikus geometria

A számítási geometria az algoritmus területe, amely a geometriai fogalmakat manipuláló algoritmusokkal foglalkozik .

Definíció és első példák

Az algoritmikus geometria a geometriai objektumokkal manipuláló algoritmusok vizsgálata . Például a geometriai algoritmusok problémája az algoritmikus probléma, amely a koordinátáikkal leírt síkbeli pontok halmazából adódik a legkisebb távolságú pontpár megtalálásában .

Előzmények és felhasználások

A tudományág egyik eredete az a tény, hogy a számítógépes modellek, vagyis a virtuális valóság helyettesítik az 1970-es évekbeli tárgyak tervezésének modelljeit, amelyek ezután lehetővé teszik a valós jelenségek sokféle tanulmányozását. A számítástechnikai geometria fejlődéséhez kétségkívül a történelem szempontjából kétségkívül leginkább hozzájáruló tudományterület a számítógépes grafika . Jelenleg azonban a számítási geometria gyakran részt vesz az általános algoritmikus problémákban.

Az algoritmikus geometriát manapság a számítógépes grafikában, a robotikában, a földrajzi információs rendszerekben és a számítógépes tervezésben használják.

Klasszikus adatstruktúra

Néhány olyan feladat, amely a probléma kezdetén vagy az algoritmus belsejében használható, központi szerepet játszik az algoritmikus geometriában: poliéderek , Voronoi-diagramok és háromszögelések .

Klasszikus problémák

Konvex boríték

A sík ponthalmazának domború burkolata a legkisebb konvex sokszög, amely tartalmazza az összes pontot. Ez a fogalom azonnal általánosítható 2-nél nagyobb dimenziókra.

A jelenleg legismertebb algoritmus, amely lehetővé teszi bármely n pont halmazának konvex burkolatának meghatározását 2D-ben ( Graham útja ) vagy 3D- ben O-ban van ( n log ( n )) . Az adatok további ismerete nélkül nem lehet jobb, mint Ω ( n log ( n )); azonban számos O ( n ) algoritmus létezik az egyszerű sokszögek (nem önmagukat metsző sokszögek) esetének kezelésére, amelyeket a pontok megjelenési sorrendjében adunk meg. Vannak olyan algoritmusok is, amelyekben a bonyolultságot az n pontok számának függvényében adják meg, de a konvex borítékban lévő pontok h számának függvényében (azaz az algoritmus kimenetén): a Jarvis-séta egy algoritmus O-ban. ( nh ) és Chan algoritmusa O-ban van ( n log h ).

Bármely d ( d > 3) dimenzió esetén a legismertebb algoritmusok vannak . Θ(n⌊d2⌋){\displaystyle \Theta (n^{\lfloor {\frac {d}{2}}\rfloor })}

Általános algoritmikus problémák

Az algoritmikus geometria optimális megoldásokat kínál a korlátozott univerzumban leírt problémákra. Valóban, ez a probléma a 2. dimenzió korlátozott rácsán [1, X ] × [1, Y ] elrendezett pontok vonatkozásában foglalkozik. Tágabb értelemben ugyanezekkel a problémákkal foglalkozik a nagyobb dimenziós rácsokon és a egész számok (1. dimenzió).

Például adott ponthalmaz S az intervallum egész [1, U ], lehetséges, hogy kihasználják a korlátos jellege a világegyetem [1, U ] megoldani bizonyos problémákat az alábbiakban bonyolultságuk minimálisak határtalan univerzumban . A legtriviálisabb és legismertebb eset a lineáris válogatás , a vödör jön ki . Az S elemei időben rendezhetők | S | + U egyszerre böngészve az S- t, és minden elemet tárol a "vödörben", amely az 1-től U- ig számozott vödör-sorozatnak felel meg .

Számos algoritmikus probléma talál optimális megoldást egy korlátozott univerzumban:

• Adva egy S számosságot n egész szám intervallumban [1, U ],
  • A q-fast-trie felépítésének köszönhetően log ( n ) helyett időben kapja meg az S- nek egy adott x-hez legközelebb eső elemét .log⁡(U){\displaystyle {\sqrt {\log(U)}}}
• Adott egy S halmaz egy rácson [1, U ] x [1, U ].
  • A k + log ( n ) helyett kapja meg az összes pontot, amely az x pontot uralja a két koordinátájukon a k + log (log ( U )) időben, ha k a válaszok száma . Lásd még hatótávolság keresés ( Tartomány keresés ).
• Adott I intervallumkészlet az [1, U ] intervallumon ,
  • Találd meg az összes időközönként I amelyek átmennek egy adott pont x időben k + log (log ( U )) helyett k + log ( n ), ha k is a válaszok száma, köszönhetően a fa struktúra kutatás elsőbbséget.

Néhány más fontos kérdés

• Voronoi diagram és kettős gráfja a Delaunay-háromszögelés
• Két szegmens metszéspontja  (be)
• Két vonal metszéspontja  (be)
• A két legközelebbi pont megkeresése
• Sokszög háromszögelése
• Művészeti galéria probléma

Nehézségek és technikák

Az egyik nehézség a dimenzió pestise  : a klasszikus algoritmusok használhatatlanná válnak, ha az adatok nagy térhez tartoznak. Klasszikus technika a valószínűségi algoritmusok használata .

Megjegyzések és hivatkozások

1. Francis Lazarus, „  Algoritmikus geometria: előadási jegyzetek  ” , a Laboratoire GIPSA-n
2. Jean-Daniel Boissonnat , „  Algoritmikus geometria: a geometriai adatoktól az adatgeometriáig  ” , Collège de France-on .

Lásd is

Kapcsolódó cikkek

• Számítási geometria (egyértelműsítés) 

Külső linkek

• Bevezetés a modellezésbe és a geometriai algoritmusokba