Convex hull

Extreme points

Dalam geometri, convex hull adalah himpunan cembung terkecil yang berisi himpunan itu sendiri. Convex hull dapat didefinisikan sebagai irisan dari semua himpunan cembung yang berisi himpunan bagian tertentu dari ruang Euklides, atau sebagai himpunan semua kombinasi cembung dari titik-titik dalam subhimpunan tersebut. Untuk suatu subhimpunan terbatas, convex hull dapat divisualisasikan sebagai bentuk yang dikelilingi oleh karet gelang yang direntangkan di sekitar subhimpunan.

Convex hull dari himpunan terbuka adalah himpunan terbuka, dan convex hull dari himpunan kompak adalah himpunan kompak. Setiap himpunan cembung kompak adalah convex hull dari titik ekstremnya. Operator convex hull adalah contoh dari operator ketertutupan, dan setiap antimatroid dapat dinyatakan dengan menerapkan operator ketertutupan tersebut pada himpunan titik terhingga. Masalah algoritmik untuk menemukan convex hull dari himpunan titik terhingga pada bidang atau ruang Euklides berdimensi rendah lainnya, dan masalah dual dari mengiris ', merupakan masalah mendasar dalam geometri komputasi. Algoritma-algoritma tersebut dapat diselesaikan dalam waktu $O(n\log n)$ untuk himpunan berisi titik-titik dalam ruang dua atau tiga dimensi, dan dalam waktu yang mencocokkan kompleksitas output worst-case yang diberikan oleh teorema upper bound dalam dimensi yang lebih tinggi.

Selain himpunan berisi titik-titik terhingga, convex hull juga dipelajari untuk memahami poligon sederhana, gerakan Brown, kurva ruang, dan epigraph fungsi. Convex hull mempunyai banyak penerapan dalam matematika, ekonomi, optimisasi kombinatorik, pemodelan geometris, dan etologi. Struktur yang berkenaan dengannya adalah ', ', triangulasi Delaunay dan diagram Voronoi, serta '.

Definisi

Himpunan titik-titik di ruang Euklides didefinisikan sebagai himpunan yang cembung atau konveks apabil himpunan tersebut mengandung ruas-ruas garis yang terhubung oleh pasangan titik. Convex hull dari suatu himpunan tertentu $X$ dapat didefinisikan sebagai

1. Himpunan cembung minimum (yang unik) yang mengandung himpunan $X$
2. Irisan dari semua himpunan cembung yang mengandung himpunan $X$
3. Himpunan dari semua kombinasi cembung yang berisi titik-titik di himpunan $X$
4. Gabungan dari semua simpleks dengan titik-titik pertemuan (verteks) di himpunan $X$

Untuk himpunan terbatas di ruang Euklides, tidak semua pada segaris, batas dari convex hull adalah kurva tertutup sederhana dengan keliling minimum yang mengandung $X$. Convex hull dapat dibayangkan seperti meregang sebuah karet gelang yang mengitari seluruh himpunan $S$ dan kemudian melepaskannya hingga menyusut. Pada saat karet gelang itu menjadi tegang, karet tersebut menutupi convex hull dari $S$. Formulasi tersebut secara langsung tidak berlaku untuk dimensi yang lebih tinggi: untuk suatu himpunan dengan titik-titik terhingga di ruang berdimensi tiga, suatu kitaran dari pohon rentang dari titik-titik menutupinya dengan sembarang luas permukaan yang kecil, lebih kecil dari luas permukaan dari convex hull. Akan tetapi, dalam dimensi yang lebih tinggi, berbagai ragam masalah hambatan dalam mencari permukaan energi minimum atas suatu bentuk yang diketahui dapat memiliki convex hull sebagai solusinya.

Untuk objek dalam tiga dimensi, definisi pertama berbunyi bahwa convex hull adalah ' objek yang cembung sekecil mungkin. Definisi yang menggunakan irisan dari himpunan cembung dapat diperluas ke bidang geometri non-Euklides. Definisi yang menggunakan kombinasi cembung dapat diperluas dari ruang Euklides ke sembarang ruang vektor real atau ruang affine. Convex hull dapat diperumum dengan cara yang lebih abstrak, seperti ke '.

Pranala luar

• "Convex Hull" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29056790 (2026-03-21T11:34:04Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.