LEGKISEBB KÖR

Maga a feladat: van egy ponthalmazom és meg kell határozni azt a legkisebb sugarú kört, amelyik tartalmaz(benne vagy rajta vannak) valamennyi pontot a ponthalmazból.

Ez a probléma az egyik legrégibb multú feladat a komputacionális geometriából, már a XIX. század közepén foglalkoztak vele, mondjuk akkor még nem tekintették külön tudományágként a komputacionális geometriát.

1972(Elzinga és Hearn)-ben megjelent az első O(n²) bonyolultságú algoritmus a feladat megoldására, amit 1975(Shamos és Hoey)-ben követett is egy O(n logn) bonyolultságú, de a nagy meglepetést Nimrod Megiddo 1983-ban bemutatott lineáris megoldása jelentette. A mi megoldásunk egy 1885-ben Prf. Chrystal által bemutatott algoritmus. Igaz O(n³) bonyolultságú, de ennek a bekövetkezésének a valószínűsége viszonylag nagyon kicsi, az okokról, amiért ezt választottuk majd később írunk.

Maga az algoritmus:

Legelőször is észrevehető, hogy ez a kör függ a ponthalmaz konvex burkolójától, mert azok a pontok, melyeket a kör érint, mind rajta vannak a konvex burkolón. Ezért legelőször meghatározzuk a ponthalmaz konvex burkolóját, és nevezzük el H-nak; ez lineáris idő alatt megvan.

A következő lépésben kiválasztunk tetszőlegesen egy oldalt a konvex burkolóból, legyen ennek a neve S .

Ezután következhet az algoritmus fő része:

1. A H minden szögpontjára, melyik nincs rajta az S szakaszon, kiszámítjuk az S-el bezárt szögét. A legkisebb ilyen szög legyen a V szögpontnál és a mérete legyen a.

· Ha a nagyobb vagy egyenlő mint 90 fok, akkor kész vagyunk, mert a kör átmérője az S szakasz lesz.

· Ha a kisebb mint 90 fok, akkor továbblépünk a 2. lépésre.

2. Mivelhogy a kisebb, mint 90 fok, ellenőriznünk kell az S és a V által alkotott háromszög szögeinek a mértékét.

· Ha nincs tompa szög, akkor kész vagyunk, a keresett kör az S és a V által alkotott háromszög köré írt kör középpontja lesz.

· Ha van tompa szög, akkor az új S a tompa szöggel levő oldal lesz és megismételjük az algoritmus fő részét az 1. lépéstől.

Elemzés:

Az algoritmus bonyolultsága O(n³), mert a fő rész lineáris a konvex burkoló szügpontjainak a számával, de ezt a fő részt legrosszabb esetben majdnem n²-szer ((n-1)²/2) kell elvégezni, mert ennyi a lehetséges élek száma. Ezért kezdtük a konvex burkoló meghatározásával, mert ezzel lineárisan egy pár pontot már ki lehet zárni, máskülönben az algoritmus helyes lenne ennek a meghatározása nélkül is.

Az egyik oka ennek az algoritmusnak a választásának, az volt, hogy a többi módszerhez képest ez elég könnyű volt implementálni.

A másik ok, amelyik már sokkal lényegesebb a program szempontjából is, az hogy nagyon hatékony további új adatok bevitelénél, mert ekkor az algoritmus nem kell megint mindent újra kiszámítson, hanem a fő részt kell megint futtassa az utoljára inicializált S oldallal, annyi kivétellel, hogy most az új pontot is leelenőrzi, nemcsak a konvex burkoló szögpontjait.