Geometry Problem

Geometri komputasi adalah cabang ilmu computer yang mempelajari algoritma untuk memecahkan masalah geometris. Dalam teknik matematika modern, komputasi geometri memiliki aplikasi dalam bidang seperti computer grafis, robotika, pemodelan molekul, metalurgi, manufaktur, tata letak tekstil, kehutanan, dan statistik. Input untuk masalah komputasi geometri biasanya merupakan deskripsi masalah dari satu set objek geometris, seperti satu set poin, satu set segmen garis, atau simpul polygon. Outputnya dapat berupa garis berpotongan, atau mungkin objek geometris baru, seperti convex hull dari himpunan beberapa titik.

1.       Closest pair problem

-          Pasangan terdekat, diberikan poin n pada ruang metric, mencari pasangan terdekat antar poin

Contoh :

Closest pair menggunakan algoritma divide & conquer

Case : Menemukan dua titik yang jaraknya paling minimal dari garis S.

1.       Kita bagi menjadi dua bagian yaitu S1 dan S2 dengan garis m.

2.       Asumsikan bahwa {p1 dan p2} adalah point yang paling dekat di S1, lalu {q1 dan q2} adalah point yang terdekat di S2.

3.       Cari titk terdekat dari garis m pada bagian S1 dan S2 yaitu {p3 dan q3}.

4.       Selanjutnya pasangan titik yang jaraknya paling minimal pada garis S.

        Terdapat tiga kandidat :

{p1,p2}

{q1,q2}

{p3,q3}

Perhatikan : pasangan terdekat memiliki satu titik kontribusi dari masig-masing bgian S1 dan S2, maka kedua titik tersebut harus berada dalam area d dari garis tengah m.

KENAPA INI? Jika salah satu dari titik-titik ini adalah jauh dari titik tengah, maka tidak mungkin lebih dekat daripada unit d ke titik di bagian lain, dan karenanya tidak mungkin menentukan sepasang lebih dekat daripada d, yang telah ditetapkan sebagai minimal dua sub-solusi dihitung untuk S1 dan S2.

Kami membuat satu pengamatan akhir untuk meraih algoritma yang efisien: karena jarak minimum antara sub-solusi itu d, hanya ada maksimum satu titik dalam d m di setiap bagian S1 dan S2. Jika tidak, dua poin dalam interval yang akan menentukan pasangan dalam salah satu subset dekat daripada d, yang bertentangan dengan minimalitas d.

Oleh karena itu dalam rangka untuk melihat dari tiga pilihan kami adalah pasangan yang paling dekat yang benar, kita hanya perlu untuk menguji satu pasang poin untuk melihat apakah ada sepasang {p3, Q3} yang mendefinisikan pasangan lebih dekat daripada d! Oleh karena itu penggabungan solusi kami tentu dilakukan dalam waktu linier, jadi kami memang menggambarkan sebuah O (nlogn) algoritma.

Sumber : http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPair1D.html

2.       Convex-hull problem

-          Poligon, meminta untuk menemukan polygon cembung terkecil yang akan mencakup semua poin dari himpunan.

Contoh convex-hull :