Masalah Geometri Analisis Algoritma

Masalah Geometri

Pengertian Utama.

            Geometri dalam Bahasa Yunani Kuno, geo yang berarti “bumi” metron “pengukuran” adalah cabang matematika yang bersangkutan dengan bentuk, ukuran, posisi, poligon, dan sifat ruang. Sedari dulu orang-orang Yunani Kuno tertarik dengan pengembangan algoritma untuk memecahkab berbagai masalah. Selama 2000 tahun, minat terhadap algoritma menghilang, dan mulai bangkit kembali pada era computer modern dengan penguasaan bit, byte, dan kecerdasan buatan.

Masalah yang biasa dihadapi dalam geometris (Geometric Problem) :

-          The Closets Pair Problem

Diberikan titik pada suatu bidang dan menemukan pasangan terdekatnya.

-          Convex Hull Problem

Menemukan poligon cembung terkecil yang akan mencakup semua titik/nilai yang telah ditentukan sebelumnya.

The Closets Pair Problem

The Closets Pair Problem (permasalahan pemasangan lemari) adalah permasalahan umum yang biasa ditemui dalam konteks geometri ruang dan optimasi jarak. Dalam kehidupan sehari – hari juga banyak ditemui permasalahan seperti ini. Akan tetapi, seringkali kasus nyata memiliki batasan yang cukup tinggi sehingga terkadang solusi dengan algoritma brute force tidak dapat menyelesaikan permasalahan dengan ringkas. Permasalahan pemasangan lemari ini merupakan salah satu permasalahan klasik dalam dunia matematika diskrit.

Secara umum, permasalahan ini sering dikaitkan dengan permasalahan pada dunia kehidupan sehari – hari. Contoh permasalahannya seperti proses pengambilan dua bahan baku oleh lengan robot pada pabrik mikroprosesor agar pergerakan lengan robot seminimal mungkin. Kurang lebih permasalahan ini dapat diselesaikan dengan algoritma brute force yang membutuhkan kompleksitas waktu O(N2 ). Untuk N yang besar (N > 100000), komputasi dengan algoritma brute force akan memakan waktu yang lama, bahkan dengan komputer paling cepat saat ini.

Convex Hull Problem

Convex Hull Problem adalah permasalahan di mana kita diminta untuk membentuk suatu curva yang mampu mengcover semua himpunan titik dengan jumlah garis yang paling minimal. Jadi misalkan ada segerombol kambing di padang rumput, yang di asumsikan sebagai Covex Hull . Bagaimana cara kita untuk membuat kandang dengan bahan seminimal mungkin .
Jadi masalahnya ketika kita diminta menentukan himpunan titik yang membentuk convex hull itu sendiri dengan cara menulis program tersebut. Kompleksitas untuk menentukan himpunan convex hull adalah O(N3). Definisi lain dari convex hull adalah poligon yang disusun dari subset titik sehingga tidak ada titik dari himpunan awal yang berada di luar poligon tersebut (semua titik berada di batas luar atau di dalam area yang dilingkupi oleh poligon tersebut).

Sumber : catatananalgo

Adj

Author & Editor

Silahkan Copy Paste Tapi Cantumin Link Sumber Ya kk (^3^) Ok | Kalo Gak Tak Tabok (---)p