A geometriai algoritmusok , a számítás a konvex burok egy algoritmikus probléma . Pontok alapján megadva a domború borítékot kiszámítja .
A ponthalmaz domború héja a legkisebb domború halmaz , amely mindet tartalmazza. Ez egy sokszög, amelynek csúcsai a halmaz pontjai. A domború boríték kiszámítása a boríték, leggyakrabban annak csúcsainak kompakt ábrázolásának kiszámításából áll.
Ez egy olyan probléma, amelynek számos alkalmazása van, például a mintafelismerésben, és amely központi szerepet játszik a számítási geometriában .
A sík eset az az eset, amikor a pontok a síkban vannak elrendezve. Az idő bonyolultságát az n bemenet pontjainak és a h burkon lévő pontok számának függvényében mérjük . Számos algoritmus létezik erre az esetre.
A Jarvis séta (vagy ajándékcsomagolási algoritmus ) ötlete az , hogy a csomagot "ajándékcsomagolásba" csomagolja ": ezt a papírt az egyik pontra felakasztjuk, kinyújtjuk, majd megfordítjuk a pontot. felhő. Az algoritmus összetettsége O (nh) .
A Graham (más néven Graham-szkennelés ) során meg kell találni a legkisebb x-tengely pontját, az összes többi pontot a vele (és az x-tengelyre) készített szögből kell rendezni, majd az egymást követő pontok hármasait figyelembe véve meghatározni, hogy melyek a borítékban vannak. Összetettsége a válogatásé , vagyis O (n.log (n)) .
A Chan algoritmus szakaszokban halad. Először a pontok felosztása több csoportban, majd e csoportok konvex borítékainak kiszámítása egy O (n.log (n)) algoritmussal (mint a Graham- séta ), végül egy Jarvis-séta e már kiszámított borítékok felhasználásával . Összetettsége O-ban van (n.log (h)) .
A Quickhull egy megosztó és meghódító algoritmus . Átlagos komplexitása O (n.log (n)). Legrosszabb komplexitása O (n²).
Shamos " algoritmus egy oszd meg és uralkodj algoritmus. Összetettsége O (n.log (n)).
A algoritmusa Kirkpatrick és Seidel (a) rendelkezik egy komplexitása O (n.log (h)) .
Más algoritmusok léteznek, például Andrew algoritmusa.
A Preparata-Hong algoritmus a 2. és a 3. dimenzióhoz működik.
2-nél nagyobb dimenziók esetén a gyorshajtásos algoritmus és Chan algoritmusa működik.
Vannak algoritmusok is a konvex burok közelítésére.