Constructing the convex hull of a partially sorted set of points

DOI10.1016/0925-7721(93)90023-YMaRDI QIDQ1803271zbMATH OpenFDO

Authors Michael T. Goodrich

Publication date 29 June 1993

Published in Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

computational geometryconvex hullpartially sorted set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Finding the convex hull of a sorted point set in parallel
• A FAST PARALLEL ALGORITHM FOR FINDING THE CONVEX HULL OF A SORTED POINT SET
• A sublogarithmic convex hull algorithm
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
• Optimal output-sensitive convex hull algorithms in two and three dimensions

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• A Lower Bound to Finding Convex Hulls
• An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
• An efficient algorithm for determining the convex hull of a finite planar set
• An optimal convex hull algorithm in any fixed dimension
• Applications of random sampling in computational geometry. II
• Finding the convex hull of a simple polygon
• Finding the convex hull of a sorted point set in parallel
• Linear Programming in Linear Time When the Dimension Is Fixed
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• On the convex layers of a planar set
• Parallel computational geometry
• The Ultimate Planar Convex Hull Algorithm?

Cited in

(8)

• A fast and efficient algorithm for determining the connected orthogonal convex hulls
• One approach to constructing a minimal convex hull
• Fast randomized parallel methods for planar convex hull construction
• Applications of a semi-dynamic convex hull algorithm
• Convex blocking and partial orders on the plane
• Calculation of partially convex hulls and approximations for finite planar sets
• Ducci iterates and similar ordering of visible points in convex regions
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing

This page was built for publication: Constructing the convex hull of a partially sorted set of points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803271)