Optimal BSR Solutions to Several Convex Polygon Problems |
| |
Authors: | Jean-Frédéric Myoupo David Semé Ivan Stojmenovic |
| |
Affiliation: | (1) Laboratoire de Recherche en Informatique d'Amiens (LaRIA), Université de Picardie Jules Verne, Faculté de Mathématiques et d'Informatique, 33 rue Saint-Leu, 80039 Amiens Cedex 1, France;(2) Computer Science, SITE, University of Ottawa, Ottawa, Ontario, K1N 6N5, Canada |
| |
Abstract: | This paper focuses on BSR (Broadcasting with Selective Reduction) implementation of algorithms solving basic convex polygon problems. More precisely, constant time solutions on a linear number, max(N, M) (where N and M are the number of edges of the two considered polygons), of processors for computing the maximum distance between two convex polygons, finding critical support lines of two convex polygons, computing the diameter, the width of a convex polygon and the vector sum of two convex polygons are described. These solutions are based on the merging slopes technique using one criterion BSR operations. |
| |
Keywords: | broadcast CRCW PRAM parallel algorithm reduction selection geometric problems |
本文献已被 SpringerLink 等数据库收录! |
|