Geometri komputasi
Dari Wikipedia, ensiklopedia bebas
Dari Wikipedia, ensiklopedia bebas
Geometri komputasi merupakan salah satu cabang ilmu komputer yang mempelajari algoritma yang dapat dinyatakan dalam istilah geometri. Beberapa masalah geometri murni muncul dari studi tentang algoritma geometri komputasi, dan masalah seperti itu juga dianggap sebagai bagian dari geometri komputasi. Geometri komputasi merupakan salah satu bidang komputasi tertua dalam sejarah sejak zaman kuno, meskipun geometri komputasi modern yang saat ini masih dalam perkembangan.[1]
Analisis algoritma adalah pusat dari geometri komputasi, yang memiliki peran signifikan dalam mengolah kumpulan data yang jumlahnya puluhan atau bahkan ratusan juta. Untuk himpunan seperti itu, perbedaan antara O ( n 2 ) dan O ( n log n ) bisa saja diartikan sebagai perbedaan antara hari dan detik dalam komputasi.
Cabang utama geometri komputasi adalah:
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 :
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.
Masalah utama dalam geometri komputasi dapat diklasifikasikan dengan cara yang berbeda, sesuai dengan kriterianya. Kelas umumnya dapat dibedakan sebagai berikut:
Masalah dalam kategori ini mencakup beberapa masukan
Dalam masalah kategori ini, beberapa masukan diberikan dan keluaran yang sesuai perlu dibangun atau ditemukan. Beberapa masalah mendasar dari jenis ini adalah:
Artikel utama: desain geometris berbantuan komputer
Cabang ini juga dikenal sebagai pemodelan geometris dan desain geometris berbantuan komputer (CAGD).
Masalah inti adalah kurva dan pemodelan dan representasi permukaan.
Instrumen terpenting di sini adalah kurva parametrik dan permukaan parametrik , seperti kurva Bézier , kurva spline , dan permukaan. Pendekatan non-parametrik yang penting adalah metode set level .
Bidang aplikasi geometri komputasi meliputi industri pembuatan kapal, pesawat terbang, dan otomotif.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.