Konveksna ogrinjača
Iz Wikipedije, proste enciklopedije
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
- Jarvishev obhod
- Grahamovo preiskovanje
- inkrementalna metoda
- algoritem tvorbe konveksne lupine s strategijo »deli in vladaj«
- aproksimacijski algoritem
Ta članek, ki se nanaša na računalništvo, je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.
Ta matematični članek je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.
