Definíció: Legyen S a Z sík egy ponthalmaza. S konvex ha tetszõleges A,B S-beli pont esetén az AB szakasz is S-be esik .

Lemma: Konvex halmazok metszete is konvex.

Tétel: Legyen  T a Z sík egy tetszõleges ponthalmaza. Ekkor létezik egyetlen egy c(T) ponthalmaz, amelyre teljesülnek az alábbiak:

• c(T) tartalmazza T-t,
• c(T) konvex,
• ha c' ponthalmazra teljesül, hogy c' is tartalmazza T-t, továbbá c' is konvex, akkor c' tartalmazza c(T)-t, azaz c(T) a legszûkebb halmaz, amely rendelkezik az elsõ két tulajdonsággal.

Megjegyzés: Azaz beláttuk, hogy: Minden T ponthalmazhoz létezik egy  ponthalmaz, amely rendelkezik a kimondott tulajdonságaival. Egzisztenciát állító tétellel állunk szemben.

Definíció: T ponthalmaz konvex burka, conv(T) a fenti tételben szereplõ c(T).

Tétel: (o) Ha P egy egy elemû ponthalmaz, akkor conv(P)=P.

(i) Legyen P egy e egyenesre esõ, nem egy elemû ponthalmaz. Ekkor conv(P) egy zárt szakasz, amely két végpontja egy-egy eleme conv(P)-nek.

(ii) Legyen P egy ponthalmaz a síkon, amely nem esik egy egyenesre. Legyen egy e irányított egyenes a P ponthalmaz támaszegyenese. Ha e-nek egyetlen közös pontja van P-vel, akkor e-nek és conv(P)-nek is egyetlen közös pontja. Ekkor e és P közös pontját P lényeges elemének nevezzük. Ha e-nek több közös pontja is van P-vel, akkor e és conv(P) közös része egy szakasz. Ebben az esetben az e támaszegyenest lényeges támaszegyenesnek nevezzük. Egy lényeges támaszegyenes és conv(P) közös részének (amely egy szakasz) két végpontja P egy-egy lényeges eleme.

(iv) A P ponthalmaz lényeges elemei konvex helyzetûek, azaz egy konvex sokszög csúcshalmazát alkotják. Ez a konvex sokszög azonos conv(P)-vel. Tehát egy véges ponthalmaz konvex burka egy konvex sokszög. Ennek a konvex sokszögnek az oldalegyenesei pontosan a lényeges támaszegyenesek egyenesei.

Bizonyítás: (i) és (ii) nyilvánvaló.

(iii) Legyen az e irányított egyenes P egy támaszegyenese, amely a P ponthalmazból egyetlen egy Q pontot tartalmaz. e zárt jobb oldala egy P-t tartalmazó konvex ponthalmaz, így conv(P) része ennek. Belátjuk, hogy conv(P) az e egyenesrõl egeytlen pontot Q-t tartalmazza. Ehhez az e egyenest forgassuk el Q körül egy kicsiny szöggel pozitív, illetve negatív irányba. Legyen e⁺ és e^- az így kapott két egyenes. Könnyû látni (mivel ponthalmazunk véges), hogy alkalmasan kicsiny szöggel dolgozva e⁺ és e^- is támaszegyenes lesz. A két támaszegyenes ad egy-egy ``üres nyilt félsíkot'', ahol az üresség a P ponthalmazra vonatkozik. A két üres félsík bizonyítja, hogy az e egyenesrõl Q-n kívül más pont nem lehet P-bõl.

Tegyük fel, hogy az e irányított egyenes P-bõl több pontot is tartalmaz. Ekkor az e egyenesre esõ pontok konvex burka egy AB szakasz lesz (tegyük fel, hogy az e irányítása szerint A a korábbi, B a késõbbi pont). A és B (az (ii) pont alapján) P egy-egy eleme. Most egy kicsiny szöggel A körül pozitív irányba forgatva e-t, illetve egy kicsiny szöggel B körül negatív irányba forgatva e-t az így kapott e⁺ és e^- irányított egyenesek P támaszegyenesei lesznek. Sõt e⁺ P-bõl csak az A, illetve e^- P-bõl csak a B pontot tartalmazza. (A kicsiny szög alatt természetesen alkalmasan kicsiny szöget kell érteni). Ezekután az állítás az elõzõ gondolatmenethez hasonlóan befejezhetõ.

(iv)

Példa: Egy konkrét eset felrajzolása a táblára, és a konvex burok ``meghúzása ''.

Probléma: Adott n pont a síkon. Határozzuk meg a konvex burkukat.

A konvex burok csúcsaira a következõ jellemzés adható:

Lemma: Legyen P egy nem egy egyenesre esõ ponthalmaz a síkon (speciálisan P elemszáma legalább 3). Legyen Q a P ponthalmaz egy eleme. Q akkor és csak akkor eleme conv(P)-nek, ha létezik R, S, T különbözõ P-beli pontok, hogy a RQS háromszög tartalmazza a P pontot.

A modell: Input n koordinátapár, azaz 2n valós szám. Elemi lépések: Két való szám összehasonlítása, alapmûveletek való számokkal.

Megjegyzés: Csak összehasonlításokkal nem határozható meg a konvex burok.

Ebbõl adódik egy algoritmus. P összes elemére vizsgáljuk meg, hogy a P P-tõl különbözõ pontjaiból alkotott hármasok által meghatározott háromszögek közül valamelyik tartalmazza-e P-t. Ha igen, akkor P nem csúcs. Ha nem, akkor P csúcs.

Elemi koordinátageometriai probléma: Adott P,Q,R,T pontok. Döntsük el P benne van-e a QRT háromszögben.

A megoldásra több lehetõség van. Néhányat ismertetünk:

I) A QRT háromszög mindegyik oldalára megnézzük, hogy a szemközti csúcs és a P pont a kiválasztott oldal oldalegyenese által meghatározott két nyilt félsík közül ugyanabba esik-e. Ha igen, akkor belsõ pont, különben nem.

II) A P csúcson keresztül egy tetszõleges félegyenest húzunk és megnézzük, hogy hány metszéspontja van a háromszög kerületével. Ezen megoldás esetén tárgyalni kell egy félegyenes és egy szakasz kölcsönös helyzetének vizsgálatát.

III) A P pontból a háromszög csúcsaiba vezetõ három vektor által bezárt szögeket kiszámítjuk. Ha a háromszög egyike sem 180^o és összegük 360^o, akkor a P pont belsõ pont. Más esetben P nem belsõ pont.

Az eljárás analízise: {n alatt 4} pontnégyes mindegyikére kell ugyanannyi (konstans) számolást, elemi lépést elvégezni. Az elemi lépések száma függ attól, hogy a koordinátageoemtriai probléma melyik megoldása szerint haladunk.

Megjegyzés: Az eljárás végén a csúcsok halmazát kapjuk meg. A kerületi sorrend nem adódik ki.

Minden pontpárra ellenõrizzük, hogy a konvex burok egy oldal szakaszát alkotják-e: Azaz egyenesük támasz egyenes-e, továbbá ponthalmazunkból az egyenesükre esõ pontok mindegyike az általuk meghatározott szakaszra esik-e?

A két ellenõrizendõ állítás elvégzése O(n) lépéssel megtehetõ. A teljes algoritmus idõigénye (ⁿ₂)O(n)=O(n^3).