Geometric Problem

Algoritma geometri berurusan dengan objek-objek geometri, seperti titik, garis, dan poligon. Orang-orang yunani jaman dahulu sangat tertarik untuk menyelesaikan bermacam masalah geometri. Lalu untuk jaman kita yang sekarang, algoritma geometri biasa digunakan untuk menyelesaikan masalah-masalah seperti komputer grafik, robotik, dan tomography.

Contoh Kasus

Closest-pair

Masalah closest-pair adalah mencari dua titik yang paling dekat dari sekumpulan n titik. Ini adalah hal paling sederhaman dari bermacam permasalahan dalam komputasi geometri. Titik dalam hal ini bisa digambarkan sebagai objek fisik seperti pesawat, pengantar surat, sampel statistik dan lainnya. Sebagai contoh untuk implementasinya, Penyedia layanan antar surat membutuhkannya untuk mencari kandidat pengantar surat terdekat.

Convex Hull

Convex Hull merupakan persoalan klasik dalam komputasi geometri. Persoalannya digambarkan secara sederhana dalam ruang dimensi dua (bidang) sebagai mencari subset dari himpunan titik pada bidang tersebut sedemikian rupa sehingga jika titik-titik tersebut dijadikan poligon maka akan membentuk poligon yang konveks. Suatu poligon dikatakan konveks jika digambarkan garis yang menghubungkan antar titik maka tidak ada garis yang memotong garis yang menjadi batas luar poligon. Definisi lain dari convex hull adalah poligon yang disusun dari subset titik sedemikian sehingga tidak ada titik dari himpunan awal yang berada di luar poligon tersebut (semua titik berada di batas luar atau di dalam area yang dilingkupi oleh poligon tersebut).

Petunjuk untuk menyelesaikan persoalan ini adalah persamaan garis pada bidang. Persamaan garis pada bidang memisahkan bidang menjadi dua bagian yaitu area di sebelah kanan bidang (relatif terhadap orientasi garis). Sebagai contoh garis berorientasi adalah sumbu koordinat. Misalkan saja sumbu vertikal (ordinat, arah orientasi ke atas), seluruh titik di sebelah kanan garis ini memiliki nilai komponen koordinat horizontal (X) yang positif sedangkan seluruh titik di sebelah kiri garis memiliki nilai komponen koordinat horizontal negatif.

Petunjuk di atas dimanfaatkan dengan membuat definisi bahwa garis yang dibentuk oleh titik-titik poligon jika diasumsikan memiliki orientasi yang sama, maka setiap titik berada di sebelah kanan seluruh garis batas tersebut. Definisi ini kemudian dimanfaatkan untuk menentukan aksi awal yaitu memilih titik yang berada paling luar pertama. Mencari titik pertama cukup mudah yaitu cukup memilih titik yang memiliki nilai komponen koordinat (horizontal atau vertikal) yang ekstrim (minimum atau maksimum). Titik-titik convex hull lainnya ditentukan berdasarkan titik pertama tadi.

Sumber:

Levithin, Anany. 2007. Introduction to The Design And Analysis of Algorithms.

https://en.wikipedia.org/wiki/Computational_geometry

Selanjutnya - Numerical Problem >