Kandangin Kambing pake Convex Hull

Convex Hull adalah permasalahan di mana kita diminta untuk membentuk suatu curva yang mampu mengcover semua himpunan titik dengan jumlah garis yang paling minimal. Gini gini, misalkan ada kawanan kambing bebas di padang rumput, nah dengan menyebutnya sebagai permasalah convex hull,

kita disuruh untuk membikin kandang dengan bahan yang paling minimal, gimana? Kalo masih bingung ada gambar nih yang mungkin bisa bantu...

Kalau diatas kertas sih gampang ya, apalagi di atas photoshop lebih gampang lagi, yang jadi masalah ketika kita diminta menentukan himpunan titik yang membentuk convex hull itu sendiri pake kodingan. Sejauh yang saya ketahui, kompleksitas untuk menentukan himpunan convex hull adalah O(n³) dengan menggunakan pendekatan brute-force. Kali ini saya tidak akan memberikan pembahasan tentang algoritma convex hull, melainkan hanya pengenalan problem saja (tau gini gw ga bakal baca tulisan loe bro...). Tapi insyaAllah di tulisan selanjutnya akan saya bahas 2 algoritma tentang penyelesaian masalah ini. Jadi dinantikan saja, oke? Eh, sebelum berakhir, saya kasih petunjuk dulu tentang penyelesaian problem ini. Kata dosen saya,

"dua titik yang membentuk garis dan menjadikan semua titik sisa berada di salah satu sisi garis, adalah titik-titik kandidat convex hull"

Semakin penasaran? Kita nantikan tulisan selanjutnya, (kalau ndak males).