COMPUTATION OF THE CONVEX HULL FOR SORTED POINTS ON A RECONFIGURABLE MESH
Koji Nakano · International Journal of Parallel Emergent and Distributed Systems · 1996
This paper presents convex hulls algorithms for a sorted set of points on a word model reconfigurable mesh. The algorithms are designed for two input cases: sparse input (i.e. one point is given for each column) and dense input (i.e. one point is given for each processor). For sparse input, the convex hull of n points can be computed in O(log2 n/log2 m + 1) time on an n × m reconfigurable mesh. For dense input, the convex hull of nm points can be computed in O(log2 n/logm + log2 m) time on an n × m reconfigurable mesh. As a corollary, for every fixed ∊ > 0, an n × n ∊ reconfigurable mesh is sufficient to compute the convex hull of n points in constant time, and an n/2log2/3 n × 2log2/3 n reconfigurable mesh can compute the convex hull of n points in O(log4/3 n) time.