Geometry problem

I. Geometry problem

Dalam kehidupan kita sehari – hari kita banyak berhubungan dengan geometri . Segala bentuk dan wujud yang ada disekitar manusia didefinisikan kedalam geometri. Sejalan dengan perkembangan teknologi masalah – masalah  menjadi sangat kompleks dan menyangkut kehidupan orang banyak seperti sistem navigasi autopilot pada kendaraan , menetukan bentuk permukaan bumi dan lain sebagainya. Masalah – masalah yang menyangkut tentang geometri tersebut sangat memerlukan algoritma   yang dirancang dengan baik untuk menyelesaikannya dengan efektif dan efisien . Pada sekitar tahun 1970 disiplin ilmu geometri komputasional ditemukan untuk  menyelesaikan maslah – masalah tersebut. Geometri komputasional sendiri adalah salah satu bidang ilmu komputer yang mempelajari tentang masalah – masalah geometri.Permasalahan geometri komputasi mencakup beberapa hal, yakni trigonometri poligon (polygon triangulations), convex hulls, Voronoi diagrams, geometry searching, dan motion planning. Salah satu permasalahan yang berkaitan dengan penentuan bentuk geometri komputasi dapat diselesaikan dengan menggunakan algoritma pencarian convex hull.

Tujuan utama dari pencarian convex hull adalah menggambarkan perbedaan antar kelompok pada variabel-variabel kontinu . Adapun algoritma untuk menentukan convex hull dari himpunan titik berhingga antara lain Brute Force, Graham Scan, Jarvis March,dan Divide and Conquer. Tiap algoritma memiliki kelebihan dan kekurangan masing-masing, namun dalam kasus berdimensi dua,algoritma Graham Scan merupakan algortima yang cukup efisien dalam kompleksitas waktu yang digunakan. Salah satu pengaplikasian penggunaan convex hull adalah menetukan bentuk permukaan alam seperti yang sering digunakan dalam disiplin ilmu GIS ( Geographical Information System).

Secara umum Convex hull dapat kita nyatakan dengan adanya sejumlah titik , dimana titik – titik tersebut akan dibungkus dengan sebuah objek yang konvex dan memiliki luas/ volume sekecil mungkin . Hasil akhir yang diperoleh adalah titik –titik mana saja yang menjadi boundary/ titik keluar dan luas/volume dari Convex Hull jika diperlukan .

II Metode untuk memechkan masalah  Convex Hull 

II.1 Brute Force

Brute force search atau exhaustive search adalah teknik umum dalam memecahkan masalah. Brute force search secara sederhana mengenumerasi seluruh kemungkinan kandidat yang bisa menjadi solusi masalah dan memeriksa apakah kandidat – kandidat tersebut memenuhi seluruh solusi permasalahan. Metode ini sangat mudah diimplementasikan karena selalu mencari keberadaan solusi dari seluruh kemungkinan yang ada. Tetapi pemecahan masalah  menggunakan metode ini memerlukan waktu dan memori yang banyak sejalan dengan banyaknya permasalahan yang ingin diselesaikan .

Pencarian convex hull dengan menggunakan Brute Force ada 2 macam: Naive Brute Force dan Better Brute Force. Naive Brute Force mencari convex hull dengan cara mengiterasi seluruh titik yang ada dan mememeriksa apakah titik tersebut berada di dalam seluruh kombinasi segitiga yang dapat dibentuk oleh tiga buah titik dari titik yang lain. Sebuah titik merupakan anggota convex hull jika titik tersebut tidak terletak di dalam semua kombinasi segitiga lain tersebut. Berbeda dengan Naive Brute Force, Better Brute Force mencari convex hull dengan mencari semua kombinasi garis yang dapat dibentuk dari dua buah titik pada himpunan Q dan kemudian memeriksa apakah garis tersebut merupakan convex hull yakni dengan membandingkan keberadaan titik lain menggunakan cross product.

II.2  Graham scan

Ditemukan tahun 1972 oleh Ronald Lewis Graham seorang matematikawan berkebangsaan Amerika Serikat . Kemudian pada tahun 1981 A.C Yao membuktikn bahwa Algoritma tersebut adalah yang paling optimal untuk kondisi kasus terburu. Karena kecepatan Algoritma in adalah yang paling populer dalam pencarian Convex hull. Sayangnya ini tidak bisa digunakan pada bidang berdimensi lebih dari dua dimensi karena Garaham scan menggunakan pengurutan titik berdasarkan sudut dimana belum ada metode yang analog pada dimensi diatas dua.

 berlanjut ke page berikutnya