Konveks omhylning

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk
Den konvekse omhylningen av punkter i to dimensjoner (blå linje)
Den konvekse omhylningen av punkter i tre dimensjoner

Den konvekse omhylningen av en mengde punkter X i et euklidsk rom er den minste konvekse mengden som inneholder alle punktene fra X. I én dimensjon er dette et linjestykke, i to en polygon og i tre en polyeder.

Formelt kan den konvekse omhylningen defineres som snittet av alle konvekse mengder som inneholder X, eller som mengden av alle konvekse kombinasjoner av punkter i X. Den siste definisjonen kan også brukes til å generalisere konseptet til villkårlige reelle vektorrom, og igjen videre til alle orienterte matroider.

Å finne det konvekse hullet av et endelig antall punkter er et av de mest fundamentale problemene innen geometrisk modellering. For lavere dimensjoner finnes det flere kjente algoritmer som løser dette.

Eksterne lenker[rediger | rediger kilde]