Parallel algorithms for some functions of two convex polygons
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.
- DETERMINING THE SEPARATION OF SIMPLE POLYGONS
- A linear time algorithm for the computation of some distance functions between convex polygons
- Parallel algorithms for separation of two sets of points and recognition of digital convex polygons
- scientific article; zbMATH DE number 278832
- scientific article; zbMATH DE number 4050997
- Optimal parallel algorithms for point-set and polygon problems
- Optimal randomized parallel algorithms for computational geometry
- Finding congruent regions in parallel
- Constructing the Voronoi diagram of a set of line segments in parallel
- A parallel algorithm for finding congruent regions
- Optimal, output-sensitive algorithms for constructing planar hulls in parallel
- A nearly optimal deterministic parallel Voronoi diagram algorithm
- A parallel algorithm for computing polygon set operations
- Convexity problems on meshes with multiple broadcasting
- A time-optimal parallel algorithm for three-dimensional convex hulls
- Finding a closet visible vertex pair between two polygons
- Parallel algorithm for corner finding on digital curves
- DETERMINING THE SEPARATION OF SIMPLE POLYGONS
- Determining Weak Visibility of a Polygon from an Edge in Parallel
- Finding the Convex Hull of Discs in Parallel
- Common tangents of two disjoint polygons in linear time and constant workspace
- CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTS
- OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS
- An optimal algorithm for finding the separation of simple polygons
- An optimal algorithm for the separating common tangents of two polygons
- Comments on two parallel algorithms for the planar convex hull problem
- Optimal BSR solutions to several convex polygon problems
- An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search
- Fast randomized parallel methods for planar convex hull construction
- Parallel algorithms for separation of two sets of points and recognition of digital convex polygons
- A sublogarithmic convex hull algorithm
This page was built for publication: Parallel algorithms for some functions of two convex polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105374)
