Geometri komputasional adalah cabang ilmu komputer yang dikhususkan untuk mempelajari algoritma yang dapat dinyatakan dalam bentuk geometri. Beberapa masalah geometri murni muncul dari studi algoritma geometrik komputasional, dan masalah seperti itu juga dianggap sebagai bagian dari geometri komputasi. Sementara geometri komputasi modern adalah perkembangan terakhir, ini adalah salah satu bidang komputasi tertua dengan sejarah yang membentang kembali ke jaman dahulu.
Komputasi komputasional merupakan pusat geometri komputasi, dengan signifikansi praktis yang besar jika algoritma digunakan pada dataset yang sangat besar yang mengandung puluhan atau ratusan juta poin. Untuk set seperti itu, perbedaan antara O (n2) dan O (n log n) mungkin perbedaan antara hari dan detik perhitungan.
Dorongan utama untuk pengembangan geometri komputasi sebagai disiplin adalah kemajuan dalam grafik komputer dan desain dan manufaktur berbantuan komputer (CAD / CAM), tetapi banyak masalah dalam geometri komputasi bersifat klasik, dan mungkin berasal dari visualisasi matematis.
Aplikasi penting lainnya dari komputasi geometri termasuk robotika (perencanaan gerak dan masalah visibilitas), sistem informasi geografis (GIS) (lokasi geometri dan pencarian, perencanaan rute), desain sirkuit terpadu (desain geometri IC dan verifikasi), rekayasa yang dibantu komputer (CAE) (generasi mesh), visi komputer (rekonstruksi 3D).
Network Flow Algorithms
masalah Network Flow adalah kelas masalah komputasi di mana input adalah flow network (grafik dengan kapasitas numerik di ujungnya), dan tujuannya adalah untuk membangun flow, nilai numerik pada setiap sisi yang menghormati kendala kapasitas dan yang memiliki flow masuk sama dengan flow keluar di semua titik kecuali untuk terminal yang ditentukan.
0 comments