Geometric Problem
Berkaitan dengan objek geometrik
: titik, garis, poligon dan lain-lain
Yunani Kuno : membangun geometrik
sederhana contohnya segitiga, lingkaran dan lain-lain
Masa kini : aplikasi komputer,
grafik, robot
Masalah klasik :
- Problem closest pair : diberikan titik pada suatu bidang, dan temukan pasangan terdekatnya
- Convex hull : temukan poligon cembung terkecil yang melibatkan smeua titik yang telah ditentukan
Contoh kita akan membahas tentang
Problem closest Pair
Pembahasan Problem closest pair
Permasalahan closest pair
merupakan salah satu permasalahan klasik dalam dunia matematika diskrit. Secara
singkat, deskripsi permasalahan adalah sebagai berikut: diberikan N buah titik
yang terletak pada bidang planar 2-dimensi, tentukanlah dua buah titik yang memiliki
jarak paling dekat.
Penyelesaian untuk Problem
Closest Pair diantaranya sebagai berikut :
1. Penyelesaian Dengan Brute Force
2. Penyelesaian Dengan Divide And Qonquer
Contoh penyelesaian dengan Brute
Force
Solusi brute force untuk masalah ini
cukup straightforward : tinjau seluruh kemungkinan pasangan titik – titik kemudian
hitung jaraknya dan cari nilai maksimum. Pseudocode untuk solusi ini
adalah sebagai berikut :
Jadi, untuk setiap instance permasalahan,
akan terjadi N pass untuk setiap titik dan masing–masing pass akan melakukan
peninjauan kembali untuk N titik. Sehingga, kompleksitas waktu untuk algoritma
ini adalah O(N2).
Permasalahan closest pair adalah
permasalahan yang jamak ditemukan dalam bidang matematika diskrit geometri. Permasalahan ini pada
dasarnya hanya memiliki solusi dengan
algoritma brute force. Meskipun demikian,
terdapat sebuah rancangan solusi dengan algoritma divide and conquer yang
memiliki kemangkusa lebih baik daripada algoritma brute force.
Daftar Pustaka
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2010-2011/Makalah2010/MakalahStima2010-055.pdf
Tidak ada komentar:
Posting Komentar