Parallel algorithms for some functions of two convex polygons (Q1105374)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel algorithms for some functions of two convex polygons |
scientific article |
Statements
Parallel algorithms for some functions of two convex polygons (English)
0 references
1988
0 references
Let P and Q be two convex, n-vertex polygons. We consider the problem of computing, in parallel, some functions of P and Q when P and Q are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but not two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM having \(n^{1/k}\) processors can compute the following functions in \(O(k^{1+\epsilon})\) time: (i) the common tangents between P and Q, and (ii) the distance between P and Q (and hence a straight line separating them). The positive constant \(\epsilon\) can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.
0 references
computational geometry
0 references
convex polygons
0 references
parallel algorithms
0 references
model of parallel computation
0 references
CREW-PRAM
0 references