Konveksna ogrinjača

Konveksna ogrinjača ali ~ lupina množice točk X v realnem vektorskem prostoru V je v matematiki najmanjša konveksna množica, ki vsebuje X kot podmnožico. (Pri tem je lahko X unija poljubnih množic objektov, ki jih sestavljajo točke.)

S problemom iskanja konveksne ogrinjače se pogosto ukvarja tudi računalniška geometrija. Problem si lahko predstavljamo zelo preprosto. Imejmo nekaj žebljičkov zapičenih v desko; to so točke iz X. Okoli njih razpremo elastiko tako, da so vsi žebljički v njej nato pa jo spustimo, da se napne okoli žebljičkov. Žebljički, ki se jih elastika dotika, so člani konveksne ogrinjače.

Bolj strokovno povedano je konveksna ogrinjača najkrajša možna povezava točk tako, da so vse točke na notranji strani ali člani konveksne ogrinjače.

Za reševanje konveksne lupine v računalništvu poznamo več možnih algoritmov:

• grobi pristop
• Jarvisov obhod
• Grahamovo preiskovanje
• inkrementalna metoda
• algoritem tvorbe konveksne lupine s strategijo »deli in vladaj«
• aproksimacijski algoritem