Convex omhulsel

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
De blauwe verzameling is het convex omhulsel van de rode verzameling
Convex omhulsel van een aantal punten in het vlak is een veelhoek

Het convex omhulsel of de convexe omhulling van een verzameling X van punten in de Euclidische ruimte is de kleinste convexe verzameling die X omvat.

Men kan zich het convex 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.

Een andere definitie van convex omhulsel is: de doorsnede 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 convex omhulsel de verzameling van alle convexe combinaties van de punten x1 ... xn 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^n_{i=1} \alpha_i = 1 ,{\alpha_{i}} \ge 0 \right\}

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

Het convex 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 convex 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 convex 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 convex omhulsel van de verzameling liggen. Het volstaat dus om de punten op het convex 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.