Parallel algorithms for some functions of two convex polygons

DOI10.1007/BF01762130zbMath0648.68061MaRDI QIDQ1105374

Michael T. Goodrich, Mikhail J. Atallah

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmsconvex polygonscomputational geometrymodel of parallel computationCREW-PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items

An optimal algorithm for finding the separation of simple polygons ⋮ A time-optimal parallel algorithm for three-dimensional convex hulls ⋮ Finding a closet visible vertex pair between two polygons ⋮ OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS ⋮ Optimal, output-sensitive algorithms for constructing planar hulls in parallel ⋮ An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search ⋮ A sublogarithmic convex hull algorithm ⋮ Optimal parallel algorithms for point-set and polygon problems ⋮ Optimal randomized parallel algorithms for computational geometry ⋮ Fast randomized parallel methods for planar convex hull construction ⋮ Constructing the Voronoi diagram of a set of line segments in parallel ⋮ CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTS ⋮ A nearly optimal deterministic parallel Voronoi diagram algorithm ⋮ Determining Weak Visibility of a Polygon from an Edge in Parallel ⋮ Finding the Convex Hull of Discs in Parallel

Cites Work

• Unnamed Item
• Parallel computational geometry
• Maintenance of configurations in the plane
• Computing the extreme distances between two convex polygons
• Convex hulls of finite sets of points in two and three dimensions