Geometry Problem

• ·         Berkaitan dengan objek geometrik : titik, garis. poligon dan lain-lain
• ·         Yunani Kuno : membangun geometrik sederhana contohnya segitiga, lingkaran dan lain-lain
• ·         Masa kini: aplikasi komputer • grafik, robot
• ·         Masalah:

o   Convex Hulls

o   Voronoi diagrams and Delaunay triangulations

o   arrangements, plane sweep, duality

o   geometric optimization, linear programming, complexity, and applications

o   Range searching and point location

o   Decomposition and partitioning

o   Farthest pair and closest pair problems

o   Intersection algorithms

Sedangkan komputasi Geometri itu sendiri merupakan cabang ilmu komputer yang berkaitan dengan desain dan analisis algoritma dan struktur data untuk perhitungan yang berkaitan dengan benda-benda geometris (seperti titik, garis, segmen garis, bidang, dll) atau dalam konteks geometris.

1. Diagram Voronoi

          Diagram voronoi adalah salah satu cabang ilmu yang dipelajari dalam perkuliahan geometri komputasi yang muncul pada abad ke-17. Diagram voronoi pertama kali dipikirkan oleh Rene Descartes pada tahun 1644 dan digunakan oleh Dirichlet pada tahun 1850. Kemudian Voronoi pada tahun 1907 mengembangkannya ke dalam dimensi yang lebih tinggi. Walaupun demikian, Voronoi dan Dirichlet adalah orang yang pertama kali memperkenalkan konsep diagram voronoi secara formal. Mereka menerapkan konsep tersebut dalam kajian bentuk kuadrat. Hasil dari studi tersebut kemudian disebut Dirichlet tessellation atau Voronoi diagram. Salah satu penggunaan diagram voronoi yang paling spektakuler adalah analisis penyakit kolera di London pada tahun 1854, dimana fisikawan John Snow menemukan hubungan yang kuat anatara kematian dengan penggunaan air pompa yang terinfeksi di Broad Street.

Diagram Voronoi

Secara matematis, diagram voronoi di definisikan sebagai berikut:

Misal P adalah himpunan n (jarak titik-titik dalam sebuah bidang). Diagram Voronoi dari P adalah pembagian bidang tersebut dalam n sel (bagian), satu untuk setiap titik.Titik qterletak pada sel (bagian) yang sesuai dengan titik  p_i element of P. Persamaan matematisnya adalah:

Batas dari dua daerah voronoi dismbolkan V(S) dan disebut voronoi edge (rusuk voronoi), jika terdiri lebih dari satu titik. Titik sudut dari rusuk voronoi disebut Voronoi vertices(sudut voronoi); yang dibatasi oleh tiga atau lebih daerah voronoi.

Diagram voronoi untuk 11 titik pada bidang Euclid.

Dengan mengajarkan siswa tentang diagram voronoi, mereka akan dapat mengembangkan kemampuan spatial reasoning mereka. Hal ini dapat dilakukan dengan menggunakan pendekatan matematika realistik, yaitu dengan memulai memberikan soal atau masalah konteks bagi siswa. Misalnya ada lima kantor pos yang ada di wilayah kota Palembang. Bagaimana caranya gar pelanggan atau masyarakat mengetahui kantor pos mana yang paling dekat didaerah mereka? Pertanyaan ini dapat diselesaikan dengan menggunakan konsep atau pengetahuan tentang diagram voronoi.

Daftar Pustaka:

http://analisis-algoritma12.blogspot.co.id/2016/09/geometry-problem.html

https://bustangbuhari.wordpress.com/2011/10/10/voronoi-diagram-sebuah-pengantar/

Baca juga :

Algoritma Pencarian (Searching)

Algoritma Penurutan (Sorting)

String Matching

Combinatorial Problem

Graph Problem

Numerical Problem

Geometry Problem