La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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 Algorithmes parallèles optimaux ronds pour l’enveloppe convexe de points triés

Naoki OSHIGE, Akihiro FUJIWARA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous présentons des algorithmes parallèles déterministes pour l'enveloppe convexe de points triés et leur application à un problème connexe. Les algorithmes sont proposés pour le modèle multi-ordinateur à grains grossiers (CGM). Nous proposons d'abord un algorithme parallèle optimal en termes de coût pour calculer le problème avec un nombre constant de cycles de communication pour n/p p2, Où n est la taille d'une entrée et p est le nombre de processeurs. Nous proposons ensuite un algorithme de coût optimal, plus compliqué, pour n/p pε, où 0 < ε < 2. À partir des deux résultats ci-dessus, nous pouvons calculer l'enveloppe convexe des points triés avec O(n/p) un temps de calcul et un nombre constant de tours de communication pour n/p pε, où ε > 0. Enfin, nous montrons une application de nos algorithmes de coque convexe. Nous résolvons les couches convexes pour d lignes dans O((n enregistrer n)/p) temps de calcul avec un nombre constant de tours de communication. L’algorithme est également optimal en termes de coût pour le problème.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1152-1160
Date de publication
2001/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières