Parallel Algorithms for Convex Hull Problems and Their Paradigm(Special Issue on Algorithm Engineering : Surveys)

概要

論文の詳細を見る
A convex hull is one of the most fundamental and interesting geometric constructs in computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms. Most of our discussion uses the PRAM(Parallel Random Access Machine)computational model, but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coares grained multicomputers like BSP and LogP.
社団法人電子情報通信学会の論文
2000-03-25