Nama : Nova Istiqomah
NPM : 20312064
Kelas : IF 20 A
Geometric Problem itu
adalah algoritma yang menyelesaikan permasalahan algoritma tentang geometri.
Berhubungan dengan titik, garis, poligon, dan lainnya.
Masalah klasik dalam
Geometric Problem :
1. Problem Closest Pair: diberikan titik pada sebuah bidang dan
menemukan pasangan terdekatnya.
2. Convex Hull: menemukan poligon cembung terkecil yang melibatkan
semua titik yang telah ditentukan.
Problem Closest
Pair adalah
suatu algoritma yang memecahkan persoalan untuk mencari jarak terdekat antara
kumpulan titik dalam suatu bidang dua dimensi. Cara yang paling sederhana untuk
menyelesaikan masalah ini dengan cara membandingkan semua kemungkinan
titik-titiknya untuk dicari jarak nya. Algoritma akan mencoba semua kemungkinan
titik titiknya hingga mendapatkan nilai akhir yang paling kecil.
Convex Hull adalah sebuah
permasalahan yang digambarkan secara sederhana dalam ruang dua dimensi sebagai
mencari subset dari himpunan sebuah titk-titik pada bidang dua dimensi tersebut
sehingga jika titik-titik tersebut dijadikan poligon maka akan membentuk sebuah
poligon konveks. Atau dapat diartikan dengan poligon yang disusun dari subset
titik, sehingga tidak ada titik dari himpunan awal yang berada di luar poligon
tersebut.
Untuk menyelesaikan
persoalan ini adalah persamaan garis
pada sebuah bidang. Persamaan garis pada bidang memisahkan bidang menjadi dua
bagian. Yang pertama area di sebelah kanan
bidang (relatif terhadap orientasi garis). Contohnya adalah garis yang berorientasi yaitu sumbu koordinat.
Misalnya garis yang dibentuk oleh titik-titik poligon jika memiliki orientasi
yang sama, maka setiap titik akan berada di sebelah kanan seluruh garis
tersebut.
Definisi di atas dapat
diartikan untuk menentukan aksi awal,
yaitu memilih titik yang berada paling luar pertama. Mencari titik yang
memiliki nilai komponen koordinat (horizontal atau vertikal) yang ekstrim
(minimum atau maksimum). Titik-titik convex hull lainnya ditentukan berdasarkan
titik pertama tadi.
