GEOMETRIC PROBLEM

Nama : Silvia Ranti

NPM : 20312073

Kelas : IF 20A

Mata Kuliah : Analisis Dan Strategi Algoritma

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.