Selubung cembung

Dalam geometri, lambung cembung adalah set cembung terkecil yang berisi itu. Lambung cembung dapat didefinisikan sebagai persimpangan dari semua set cembung yang berisi himpunan bagian tertentu dari ruang Euclidean, atau setara dengan himpunan semua kombinasi cembung titik-titik dalam subset tersebut. Untuk subset bidang yang dibatasi, cembung cembung dapat divisualisasikan sebagai bentuk yang dikelilingi oleh karet gelang yang direntangkan di sekitar subset.

Cangkang set terbuka terbuka, dan cangkang cangkok set kompak. Setiap set cembung kompak adalah cembung titik ekstrimnya. Operator convex hull adalah contoh dari operator penutupan, dan setiap antimatroid dapat diwakili dengan menerapkan operator penutupan ini pada set poin yang terbatas. Masalah algoritmik untuk menemukan lambung cembung dari himpunan titik hingga pada bidang atau ruang Euclidean berdimensi rendah lainnya, dan masalah rangkapnya memotong setengah ruang, merupakan masalah mendasar dari geometri komputasi. Mereka dapat diselesaikan tepat waktu $O(n\log n)$ untuk set titik dua atau tiga dimensi, dan dalam waktu yang cocok dengan kompleksitas keluaran terburuk yang diberikan oleh teorema batas atas dalam dimensi yang lebih tinggi.