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 half-space [en], merupakan masalah mendasar dalam geometri komputasi. Algoritma-algoritma tersebut dapat diselesaikan dalam waktu ${\displaystyle 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 orthogonal convex hull [en], convex layers [en], triangulasi Delaunay dan diagram Voronoi, serta convex skull [en].

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 ${\displaystyle X}$ dapat didefinisikan sebagai^[1]

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

Untuk himpunan terbatas di ruang Euklides, tidak semua pada segaris, batas dari convex hull adalah kurva tertutup sederhana dengan keliling minimum yang mengandung ${\displaystyle X}$. Convex hull dapat dibayangkan seperti meregang sebuah karet gelang yang mengitari seluruh himpunan ${\displaystyle S}$ dan kemudian melepaskannya hingga menyusut. Pada saat karet gelang itu menjadi tegang, karet tersebut menutupi convex hull dari ${\displaystyle S}$.^[2] 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.^[3] 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.^[4]

Untuk objek dalam tiga dimensi, definisi pertama berbunyi bahwa convex hull adalah bounding volume [en] 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 oriented matroid [en].^[5]

Catatan

1. ↑ Rockafellar (1970), hlm. 12.
2. ↑ de Berg et al. (2008), hlm. 3.
3. ↑ (Williams & Rossignac 2005). Lihat pula jawaban Douglas Zare mengenai pertanyaan, "the perimeter of a non-convex set", MathOverflow, 16 Mei 2014.
4. ↑ Oberman (2007).
5. ↑ Knuth (1992).

ReferensinsiReferensi

• de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. (2008), Computational Geometry: Algorithms and Applications (Edisi 3rd), Springer
• Knuth, Donald E. (1992), Axioms and Hulls, Lecture Notes in Computer Science, vol. 606, Heidelberg: Springer-Verlag, doi:10.1007/3-540-55611-7, ISBN 3-540-55611-7, MR 1226891, S2CID 5452191, diarsipkan dari asli tanggal 2017-06-20, diakses tanggal 2011-09-15
• Oberman, Adam M. (2007), "The convex envelope is the solution of a nonlinear obstacle problem", Proceedings of the American Mathematical Society, 135 (6): 1689–1694, doi:10.1090/S0002-9939-07-08887-9, MR 2286077

• Rockafellar, R. Tyrrell (1970), Convex Analysis, Princeton Mathematical Series, vol. 28, Princeton, N.J.: Princeton University Press, MR 0274683
• Williams, Jason; Rossignac, Jarek (2005), "Tightening: curvature-limiting morphological simplification", dalam Kobbelt, Leif; Shapiro, Vadim (ed.), Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2005, Cambridge, Massachusetts, USA, June 13-15, 2005, ACM, hlm. 107–112, doi:10.1145/1060244.1060257, hdl:1853/3736, S2CID 15514388

Pranala luar

Wikibooks Algorithm Implementation memiliki halaman di:

Convex hull

• Hazewinkel, Michiel, ed. (2001) [1994], "Convex hull", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
• (Inggris) Weisstein, Eric W. "Convex Hull". MathWorld.
• "Convex Hull" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

• l
• b
• s