Jelaskan Geometri komputasi kombinatorial dari Geometri komputasi

Tujuan utama penelitian dalam geometri komputasi kombinatorial adalah untuk mengembangkan algoritme dan struktur data yang efisien untuk memecahkan masalah yang dinyatakan dalam objek geometris dasar: titik, ruas garis, poligon , polihedra , dll.

Beberapa dari masalah ini tampak begitu sederhana sehingga mereka tidak dianggap sebagai masalah sama sekali sampai munculnya komputer . Pertimbangkan, misalnya, masalah pasangan terdekat :

Diberikan n poin pada bidang, temukan dua dengan jarak terkecil satu sama lain.

Seseorang dapat menghitung jarak antara semua pasangan titik, yang mana ada n (n-1) / 2 , lalu pilih pasangan dengan jarak terkecil. Ini brute-force algoritma mengambil O ( n 2 ) waktu; yaitu waktu pelaksanaannya sebanding dengan kuadrat dari jumlah poin. Hasil klasik dalam geometri komputasi adalah perumusan algoritma yang mengambil O ( n log n ). Algoritma acak yang mengambil O ( n ) waktu yang diharapkan,  serta algoritma deterministik yang membutuhkan waktu O ( n log log n ),  juga telah ditemukan.