Geometric Problem

Algoritma geometric ini beruhubungan dengan benda benda geometri seperti titik, polygon, garis. Pada zaman dahulu di Yunani kuno untuk menyelesaikan berbagai masalah geoetris seperti bentuk segitiga, lingakaran dll. Pada zaman sekarang manusia menggunakan algoritma ini untuk robotika ataupun aplikasi computer grafis.
Disini kita akan membahas dua masalah yang sudah sangat klasik yaitu: permasalahan closest-pair dan permasalahan convex-hull
Secara singkat Permasalahan closest-pair adalah sebagai berikut diberikan N buat tiitk terletak pada bidang planar 2-dimensi tentukanlah jarak dua buah titik yang paling dekat.
Permasalahan closest-pair ini memiliki solusi algoitma brute force. Tetapi jika menggunakan algoritma brute force meskipun dengan computer yang canggih akan memakan waktu yang lama. Meskipun begitu terdapat solusi lain dengan algoritma divide and conquer

Sebuah subset S dari bidang R disebut konveks  jika dan hanya jika pada seluruh dua buah titik  sembarang p,q Œ S  dibentuk garis  yang  seluruhnya berada dalam S[1]

Gambar 2 convex set

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 dari sebuah himpunan titik Q  (CH(Q)) pada n dimensi adalah seluruh irisan  dari semua convex set yang mengandung Q.  Terlebih lanjut, untuk N buah titik p1, p2, ... pN. convex hull merupakan himpunan  convex combination  yang dinyatakan dengan

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

Source --> https://bertzzie.com/knowledge/analisis-algoritma/
                  http://galih.students.uii.ac.id/?p=47.
                  Levetin Anany. Introduction  to the Design & Analysis of Algorithms.2012

Baca Juga : Algoritma Sorting
                  Algoritma Searching 
                  Algoritma String Matching
                  Combinatorial Problem
                  Graph Problem
                  Numerical Problem