Convex omhulsel

Het convexe omhulsel of de convexe omhulling van een verzameling $X$ van punten in de euclidische ruimte, genoteerd als $\operatorname {conv} X$ , is de kleinste convexe verzameling die $X$ omvat.

Men kan zich het convexe omhulsel als volgt voorstellen: Als men de punten beschouwt als nagels die in een houten vlak steken, en men een elastiekje rond de nagels spant, dan vormt dat de rand van de convexe omhulling.

Alternatief kan men zeggen dat het convexe omhulsel van $X$ de doorsnede is van alle convexe verzamelingen $K$ die $X$ omvatten:

\operatorname {conv} X=\bigcap _{X\subseteq K\subseteq V \atop K\ \mathrm {convex} }K

Hierin stelt $V$ de (euclidische) vectorruimte voor.

Ook is het convexe omhulsel de verzameling van alle convexe combinaties van de punten $x_{1},\ldots ,x_{n}\in X$ :

\operatorname {conv} X=\left\{\left.\sum _{i=1}^{n}{\alpha _{i}\cdot x_{i}}\right|x_{i}\in X,n\in \mathbb {N} ,\sum _{i=1}^{n}\alpha _{i}=1,{\alpha _{i}}\geq 0\right\}

Nog een andere equivalente definitie van convex omhulsel is: de doorsnede van alle halfruimtes die $X$ bevatten.

Het convexe omhulsel van een verzameling van eindig veel punten is een convexe polytoop: een convexe veelhoek in twee dimensies (als alle punten op één rechte lijn liggen is het convexe omhulsel een lijnstuk); een convex veelvlak in drie dimensies.

Er zijn verschillende algoritmes bekend voor het bepalen van de convexe omhulling van een eindige verzameling punten of van andere verzamelingen. De complexiteit of rekentijd van deze algoritmes wordt gewoonlijk uitgedrukt in termen van $n,$ het aantal punten in de verzameling, en $h,$ het aantal punten op de convexe omhulling.

Voor punten in twee of drie dimensies zijn algoritmen bekend die de convexe omhulling berekenen met een looptijd in de orde $O(n\log h)$ . Voor hogere dimensies $d,$ is de looptijd van de orde $O(n^{\lfloor d/2\rfloor }).$

Het bepalen van het convexe omhulsel is een elementair probleem in de computationele meetkunde. Het is een voorbereidende stap in vele algoritmes, bijvoorbeeld bij het bepalen van de diameter van een verzameling punten, dit is de grootste afstand tussen twee punten in de verzameling. Die twee punten zullen steeds op het convexe omhulsel van de verzameling liggen. Het volstaat dus om de punten op het convexe omhulsel te bepalen en daarvan de twee punten te zoeken die het verst van elkaar liggen. Ook voor het bepalen van Voronoi-diagrammen maakt men gebruik van convexe omhulsels.