Geometry problem

Algoritma geometrik berurusan dengan benda-benda geometris seperti titik, garis, dan poligon. Orang Yunani kuno yang sangat tertarik untuk mengembangkan prosedur (Mereka tidak menyebutnya algoritma) untuk memecahkan berbagai masalah  geometris, termasuk masalah membangun geometris bentuk-segitiga sederhana, lingkaran, dan sebagainya dengan penguasa ditandai dan kompas. Kemudian, untuk sekitar 2000 tahun, minat yang kuat dalam algoritma geometrik menghilang, akan dibangkitkan di usia komputer tidak lebih penguasa dan kompas, hanya bit, byte, dan kecerdikan manusia. Tentu saja, saat ini orang yang tertarik dalam algoritma geometrik dengan aplikasi sangat berbeda dalam pikiran, seperti komputer grafis, robotika, dan tomografi.

Kami akan membahas algoritma hanya dua masalah klasik komputasi geometri. the closest-pair problem dan the convex-hull problem. the closest-pair problem ini cukup jelas diberikan n poin dalam pesawat, menemukan the closest-pair antara mereka. the convex-hull problem meminta untuk menemukan convex poligon terkecil yang akan mencakup semua poin dari himpunan.

Atau dapat disimpulkan :

• ·         Berkaitan dengan objek geometrik: titik, garis, poligon, dll.
• ·         Yunani kuno: membangun bentuk geometris sederhana –segitiga, lingkaran, dll. menggunakan penggaris dan kompas yang tidak ditandai
• ·         Masa kini: aplikasi komputer grafik, robot, tomography*
• ·         Problem klasik:

o   Problem closest-pair: diberikan n titik pada suatu bidang, temukan pasangan terdekat diantaranya

o   Problem Convex hull: temukan poligon cembung terkecil yang melibatkan semua titik yang telah ditentukan