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
    0 references
    0 references
    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

    Identifiers