Geometric
problems adalah masalah yang berkaitan dengan objek geometrik seperti titik,
garis, poligon dan lain-lain.
Yunani
Kuno : membangun geometrik sederhana contohnya segitiga, lingkaran dan
lain-lain
Masakini:
aplikasi komputer grafik, robot
Masalah
klasik :
1. Problem closest pair
Masalah closest pair of points adalah masalah menentukan pasangan titik terdekat
atau pasangan titik yang mempunyai jarak minimal di antara pasangan titik yang lain
pada bidang dengan ruang dimensi tertentu. Salah satu cara menyelesaikan
permasalahan closest pair of points adalah dengan metode divide and conquer.
Menurut Weiss (1993), metode divide and conquer terdiri dua metode, yaitu:
divide : Membuat masalah menjadi bagian yang lebih kecil dengan membagi dua
permasalahan yang dilakukan secara berulang-ulang.
conquer : Penyelesaian masalah dari sub permasalahan yang ada.
Algoritma Divide and Conquer pada Ruang Dimensi Dua
Algoritma divide and conquer ini inputnya adalah titik sebanyak n sebagai anggota dari
himpunan S. Titik sebanyak n tersebut akan disortir oleh sumbu X kemudian disortir oleh sumbu
Y. Proses tersebut terjadi perulangan sampai diperoleh jarak minimal dari pasangan dua titik.
Langkah-langkah closest pair of points dengan algoritma divide and conquer pada ruang
dimensi dua adalah sebagai berikut:
Langkah 0 : Himpunan S sebagai input, yang terdiri dari n titik.
Langkah 1 : Menentukan garis vertikal m sebagai median, yang membagi
himpunan S menjadi S1 dan S2 menurut sumbu X.
Langkah 2 : Menentukan d1 dan closest pair of points dari d1 pada S1, dan menentukan d2 dan
closest pair of points dari d2 pada S2, dengan cara recursive.
Langkah 3 : d := min (d1,d2).
Langkah 4 : Membuat jarak d ke kanan dan ke kiri dari garis m yaitu (m-d,m] sebagai P1 dan
[m,m+d) sebagai P2.
Langkah 5 : Titik pada P1 dan P2 diproyeksikan pada garis m untuk disortir terhadap sumbu Y,
maka terbentuk P1* dan P2*.
Langkah 6 : Setiap titik pada P1* akan diperiksa oleh P2*secara recursive pada daerah persegi
d x 2d untuk mencari closest pair of points yang disebut d3.
Langkah 7 : ds:= min (d,d3).
2. Convex hull
Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang
cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan
pola (pattern recognition), dan penelitian operasi.
Algoritma untuk menyelesaikan permasalahan convex hull ada banyak cara misalnya
saja dengan pendekatan brute force, algoritma gift wrapping, algoritma Graham’s Scan,
dengan metode Divide and Conquer, dll.
Pemecahan Masalah Convex Hull denganAlgoritma Divide and Conquer
o Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang
diberikan berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).
o Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan
kompleksitas waktu O(1). (Basis)
o Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B,
dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X
yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat
absis-X terbesar
o Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).
o Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H,
dengan menghitung dan mencari upper dan lower tangents untuk HA dan HB dengan
mengabaikan semua titik yang berada diantara dua buah tangen ini.
Sumber :
http://digilib.its.ac.id/ITS-paper-51121150006876/35427
http://dokumen.tips/documents/pengenalan-analisis-algoritma.html#
https://digilib.uns.ac.id/dokumen/download/6016/MTY3MTk=/Penyelesaian-masalah-closest-pair-of-points-pada-ruang-dimensi-dua-menggunakan-metode-divide-and-conquer-abstrak.pdf
informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2006.../MakalahSTMIK2007-125.pdf
Bagikan
Geometric Problems
4/
5
Oleh
Rifaldi Yunus
