Finding the convex hull of a sorted point set in parallel

DOI10.1016/0020-0190(87)90002-0zbMath0654.68047OpenAlexW2016482138MaRDI QIDQ1108791

Michael T. Goodrich

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cstech/567

zbMATH Keywords

convex hullparallel algorithmcomputational geometryCREW PRAMdivide-and-conquerparallel data structurehull tree

Mathematics Subject Classification ID

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

Related Items (11)

Optimal convergence rate of the multitype sticky particle approximation of one-dimensional diagonal hyperbolic systems with monotonic initial data ⋮ The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ A sublogarithmic convex hull algorithm ⋮ Optimal parallel algorithms for point-set and polygon problems ⋮ Fast randomized parallel methods for planar convex hull construction ⋮ Parallel algorithms for separation of two sets of points and recognition of digital convex polygons ⋮ Techniques and Open Questions in Computational Convex Analysis ⋮ ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS ⋮ Constructing the convex hull of a partially sorted set of points ⋮ Determining Weak Visibility of a Polygon from an Edge in Parallel ⋮ Finding the Convex Hull of Discs in Parallel

Cites Work

• Maintenance of configurations in the plane
• Finding the intersection of n half-spaces in time O(n log n)
• Efficient piecewise-linear function approximation using the uniform metric
• An efficient algorithm for determining the convex hull of a finite planar set
• The Ultimate Planar Convex Hull Algorithm?
• Parallel Prefix Computation
• A Lower Bound to Finding Convex Hulls
• Convex hulls of finite sets of points in two and three dimensions
• An optimal real-time algorithm for planar convex hulls

This page was built for publication: Finding the convex hull of a sorted point set in parallel