|
| volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 1 van 10 gevonden artikelen
| Titel: |
COMPUTATION OF THE CONVEX HULL FOR SORTED POINTS ON A RECONFIGURABLE MESH |
| Auteur: |
Nakano, Koji |
| Verschenen in: |
International journal of parallel, emergent and distributed systems |
| Paginering: | Jaargang 8 (1996) nr. 3-4 pagina's 243-250 |
| Jaar: |
1996 |
| Inhoud: |
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(log2n/log2m + 1) time on an n × m reconfigurable mesh. For dense input, the convex hull of nm points can be computed in O(log2n/logm + log2m) 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/3n × 2log2/3n reconfigurable mesh can compute the convex hull of n points in O(log4/3n) time. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 1 van 10 gevonden artikelen
| volgende >> |