Geometri komputasi
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:
- Geometri komputasi kombinatorial , juga disebut geometri algoritmik , yang menangani objek geometris sebagai entitas diskrit . Sebuah buku landasan dalam subjek oleh Preparata dan Shamos tanggal penggunaan pertama dari istilah "geometri komputasi" dalam pengertian ini pada tahun 1975.
- Geometri komputasi numerik , juga disebut geometri mesin , desain geometris berbantuan komputer (CAGD), atau pemodelan geometris , yang terutama berhubungan dengan representasi objek dunia nyata dalam bentuk yang sesuai untuk komputasi komputer dalam sistem CAD / CAM. Cabang ini dapat dilihat sebagai pengembangan lebih lanjut dari geometri deskriptif dan sering dianggap sebagai cabang grafik komputer atau CAD. Istilah "geometri komputasi" dalam arti ini telah digunakan sejak tahun 1971.
Geometri komputasi kombinatorial sunting
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.
Kelas masalah
Masalah utama dalam geometri komputasi dapat diklasifikasikan dengan cara yang berbeda, sesuai dengan kriterianya. Kelas umumnya dapat dibedakan sebagai berikut:
Masalah statis sunting
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:
- Convex hull : Diketahui satu set titik, temukan polihedron / poligon cembung terkecil yang berisi semua titik.
- Perpotongan ruas garis : Temukan perpotongan antara kumpulan ruas garis tertentu.
- Triangulasi Delaunay
- Diagram Voronoi : Diberikan satu set titik, partisi ruang menurut titik mana yang paling dekat dengan titik yang diberikan.
- Pemrograman linier
- Pasangan titik terdekat : Diketahui satu set titik, temukan dua dengan jarak terkecil satu sama lain.
- Lingkaran kosong terbesar : Diketahui satu set titik, temukan lingkaran terbesar dengan pusatnya di dalam cembung dan tidak ada satupun yang terlampir.
- Jalur terpendek Euclidean : Hubungkan dua titik dalam ruang Euclidean (dengan rintangan polihedral) dengan jalur terpendek.
- Triangulasi poligon : Dengan adanya poligon, partisi interiornya menjadi segitiga
- Generasi mesh
- Operasi Boolean pada poligon
Geometri komputasi numerik sunting
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.
Lihat juga sunting
Referensi sunting
- ^ "Computational Geometry - an overview | ScienceDirect Topics". www.sciencedirect.com. Diarsipkan dari versi asli tanggal 2022-07-03. Diakses tanggal 2020-08-14.