Geometric Problems

Definisi Geometric Problems

Geometric Problem merupakan suatu permasalahan yang mempelajari algoritma yang berhubungan dengan ilmu geometri : titik,garis,poligon dan lain-lain. Dengan kata lain yaitu studi tentang masalah geometris dari sudut pandang komputasi. Intinya adalah teknik-teknik untuk mendesain dan menganalisis algoritma geometrik.

Geometric Problem ini membahas tentang bagaimana membentuk poligon dari sekumpulan titik, pendeteksian suatu titik terhadap suatu poligon apakah titik itu ada dalam poligon atau tidak, proses pencarian suatu titik dalam range tertentu, yang nantinya akan diaplikasikan dalam proses pencarian sejumlah data, cara mencari titik-titik terluar, perpotongan garis dan mencari titik terdckat.

Tujuan mempelajari ilmu ini adalah bahwa algoritma geometri dapat digunakan untuk membantu manusia dalam menyelesaikan per-masalahan-permasalahan yang berhubungan dengan bentuk-bentuk geometri yang juga tentunya berhubungan dengan titik dan garis sebagai dasar dari bangun geometri.

Ada 2 topik masalah dalam penjelasan ini yaitu: closest pair problem dan convex hull problem

1. Closest Pair Problem

Closest pair problem adalah masalah dalam ilmu matematika diskrit yaitu untuk menghubungkan dua titik yang memiliki jarak terkecil. Dan algoritma yang bisa digunakan adalah pendekatan Brute Force atau Divide and Conquer. Tetapi, algoritma Divide and Conquer memiliki hasil yang lebih baik dari algoritma Brute Force. Meskipun memiliki hasil yang lebih baik tetapi menggunakan Divide and Conquer prosesnya lebih rumit dibanding dengan algoritma Brute Force karena dibutuhkan analisis yang lebih mendalam.

2. Convex Hull Problem

Pencarian convex hull dari sebuah himpunan titik Q (CH(Q)) adalah mencari sebuah convex set terkecil yang memuat seluruh titik pada Q. Convex hull dari sebuah himpunan titik Q (CH(Q)) pada n dimensi adalah seluruh irisan dari semua convex set yang mengandung Q. Definisi lain dari convex hull adalah poligon yang disusun dari subset titik sedemikian 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).

Usaha pencarian algoritma yang efisien untuk  pencarian  convex hull sudah dilakukan sejak  lama berikut adalah daftar algoritma pencarian  convex hull:

No	Algoritma	Penemu	Tahun
1	Brute Force	N/A	–
2	Graham Scan	Graham	1972
3	Jarvish March	Jarvish	1973
4	Divide and conquer	Preparata & Hong	1977
5	Monotone Chain	andrew	1979
6	Incremental	kallay	1984
7	Marriage before Conquest	Kirkpatric & Seidel	1896

Beberapa hal yang bisa diaplikasikan dari ilmu Algoritma Geometrik :

1. Computer Graphics
   Kegunaan algoritma geometri yaitu untuk menggambarkan, membuat, dan memvisualisasikan dunia nyata yang kompleks ke dunia virtual. Seperti yang sering kita lihat di film-film, video games, atau simulasi virtual.
2. Shape Reconstruction
   Yaitu merekonstruksi suatu objek 2D ke dalam model komputer 3D. Biasanya digunakan untuk pencitraan alat medis, mikroskop, geologi, dan lain-lain.
3. Computer Vision
   Yaitu untuk pemulihan struktur 3D dari gambar 2D, terutama yang menggunakan informasi stereoscopic dan gerak. Pengaplikasian ini juga termasuk segmentasi citra untuk mengekstrak sebuah informasi tentang objek dalam sebuah adegan.
4. Geographical Information Systems
   Pengaplikasian dalam bidang ini meliputi pemodelan dan perkiraan medan yang rumit, serta analisis dari klasifikasi lahan, perencanaan pembangunan, dan lainnya. Untuk sistem transportasi juga digunakan untuk perencanaan rute, pemantauan kepadatan lalu lintas, dan lain-lain.
5. Mesh Generation
   Digunakan dalam pemodelan elemen hingga struktur teknik dan cairan (Hydro dan Aero) misalnya simulasi terowongan angin, peramalan cuaca, dan lain-lain. Mesh Generation adalah aspek geometri yang terkait dengan algoritma untuk membangun pemodelan baik pada objek 2D maupun 3D.
6. Robotics
   Algoritma geometrik diperlukan untuk memecahkan masalah perencanaan gerak robot.

---

 Referensi:

• https://id.scribd.com/document/28192054/Implementasi-Algoritma-Divide-and-Conquer-Untuk-Penyelesaian-Masalah-Convex-Hull
• https://en.wikipedia.org/wiki/Closest_pair_of_points_problem
• http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2010-2011/Makalah2010/MakalahStima2010-055.pdf
• https://cumaghaya.blogspot.co.id/2016/10/geometry-problems.html