Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points Algoritma Selari Optimum Bulat untuk Badan Cembung Titik Isih

Naoki OSHIGE, Akihiro FUJIWARA

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Dalam makalah ini, kami membentangkan algoritma selari deterministik untuk badan cembung titik diisih dan penggunaannya kepada masalah yang berkaitan. Algoritma dicadangkan untuk model berbilang komputer berbutir kasar (CGM). Kami mula-mula mencadangkan algoritma selari optimum kos untuk mengira masalah dengan bilangan pusingan komunikasi yang berterusan untuk n/p p2, Di mana n ialah saiz input dan p ialah bilangan pemproses. Seterusnya kami mencadangkan algoritma kos optimum, yang lebih rumit, untuk n/p pε, di mana 0 < ε < 2. Daripada dua keputusan di atas, kita boleh mengira badan cembung bagi titik-titik yang disusun dengan O(n/p) masa pengiraan dan bilangan pusingan komunikasi yang tetap untuk n/p pε, dengan ε > 0. Akhirnya kami menunjukkan aplikasi algoritma badan cembung kami. Kami menyelesaikan lapisan cembung untuk d garisan di O((n log n)/p) masa pengiraan dengan bilangan pusingan komunikasi yang tetap. Algoritma ini juga kos optimum untuk masalah tersebut.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1152-1160
Tarikh penerbitan
2001/05/01
Diumumkan
ISSN dalam talian
DOI
Jenis Manuskrip
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
kategori

Pengarang

Kata kunci

Contents [show]