Geometric Problem

Algoritma merupakan tahapan - tahapan atau langkah - langkah dalam melakukan sesuatu, atau proses yang terstruktur dalam memecahkan suatu masalah. Jadi dalam hal ini untuk memulai suatu tahap algoritma, kita memerlukan sebuah masalah yang bisa kita cari langkah atau tahapan nya untuk di selesaikan.

Dalam dunia komputer atau informatika, algoritma di artikan sebagai suatu instruksi atau sekumpulan instruksi yang di gunakan untuk menyelesaikan suatu permasalahan yang ada.

Salah satu masalah nya yaitu Geometri problem atau permasalahan geometri. Dalam buku Anany Levitin yang berjudul "introduction to the design and analysis of algorithms : 3rd edition" menjelaskan bahwa permasalahan geometri ialah berurusan dengan benda - benda geometris seperti garis, titik dan poligon. Masalah ini sudah ada sejak jaman Yunani kuno, dimana mereka menggunakan langkah - langkah untuk menyelesaikan suatu permasalahan geometri.

Salah satu contoh permasalahan geometri adalah convex hull. Convex hull yaitu kita diminta untuk membentuk suatu curva yang mampu mengcover semua himpunan titik dengan jumlah garis yang paling minimal. Jadi ada banyak titik dalam sebuah bidang, kita di minta menarik sebuah garis untuk mencakup semua titik yang ada dalam bidang tersebut.

 

Untuk menyelesai kan permasalahan ini, terdapat berbagai cara yaitu :

• Brutoforce (Pendekatan Langsung untuk suatu Permasalahan)
• Devide Conquer (Membagi Masalah dan Menggabungkan Lagi)
• Decreate Conquer (Memperkecil masalah dan selanjutnya di gabungkan kembali)
• Transforn Conquer (Menggunakan rumus yang tepat dan sesuai dengan kebutuhan)

Disini akan di jelaskan tentang Devide and Conquer, yaitu membagi masalah untuk di uraikan lalu kita menggabungkan nya lagi untuk disusun menjadi sebuah hasil.

langkah - langkah yang harus kita lakukan dalam menyelesaikan convex hull adalah sebagai berikut :

1. Urutkan setiap titik dalam bidang (himpunan) berdasarkan absisnya.
2. Bagi semua titik sama banyak ke dalam 2 sub himpunan dan secara rekursif cari convex hull dari     masing – masing sub himpunan sampai sub himpunan terdiri dari 1 atau 2 buah titik.
3. Gabungkan dua buah himpunan convex hull yang menjadi sub himpunan
    a. Hubungkan titik tertinggi dari kedua himpunan convex hull

    b. Iterasi setiap titik searah jarum jam untuk himpunan yang berada disebelah kanan, dan berlawanan arah jarum jam pada himpunan yang berada di sebelah kiri.

    c. Hubungkan titik terendah dari kedua himpunan dan gunakan cara yang sama.

Berikut adalah contoh pseudocode dari algoritma Devide and Conquer :

convex hull dapat menggunakan algoritma divide and conquer untuk mencari titik terluar. Terjadi pembagian pada saat satu set titik akan dibagi menjadi dua area yaitu, area atas dan area bawah. Pada setiap area akan dicari titik terluar dari kumpulan titik-titik tersebut. Setelah dua area tersebut menemukan titik terluar maka kedua area tersebut akan digabungkan menjadi satu dan membentuk suatu pola seperti polygon.

Jadi metode ini biasa digunakan di kehidupan nyata dalam digital printing 3D. Dengan adanya algoritma ini, 3D printing dapat lebih mudah untuk menemukan pola.

Referensi :

https://www.google.co.id/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&uact=8&ved=0ahUKEwjig_LC-MDPAhVINY8KHb1rBFIQFgg0MAM&url=http%3A%2F%2Finformatika.stei.itb.ac.id%2F~rinaldi.munir%2FMatdis%2F2006-2007%2FMakalah%2FMakalah0607-57.pdf&usg=AFQjCNFdCfe11MQoW5jwqGgN9pPuM0Yp9g

http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2014-2015/Makalah2015/Makalah_IF221_Strategi_Algoritma_2015_078.pdf

https://mas-arif.id/pengertian-algoritma-dan-langkah-langkah-desain-analisis-algoritma/

Levitin, Anany. The Design and Analysis of Algorithms.