Space-efficient planar convex hull algorithms

DOI10.1016/j.tcs.2003.05.004zbMath1068.68153OpenAlexW1973037646WikidataQ57009423 ScholiaQ57009423MaRDI QIDQ596137

Pat Morin, Jason Morrison, Hervé Brönnimann, Jyrki Katajainen, John Iacono, Godfried T. Toussaint

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.05.004

zbMATH Keywords

Computational geometryConvex hulls

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

An in-place algorithm for Klee's measure problem in two dimensions ⋮ In-place algorithms for computing (Layers of) maxima ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ A new active convex hull model for image regions ⋮ Line-segment intersection made in-place ⋮ Memory-constrained algorithms for simple polygons ⋮ Reprint of: Memory-constrained algorithms for simple polygons ⋮ Convex-hull algorithms: implementation, testing, and experimentation ⋮ A new algorithm for computing the convex hull of a planar point set ⋮ Prune-and-search with limited workspace ⋮ Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time ⋮ Convex hull properties and algorithms ⋮ Unnamed Item ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection

Uses Software

• heapsort

Cites Work

• Unnamed Item
• Unnamed Item
• Randomized quickhull
• Stable in situ sorting and minimum data movement
• Another efficient algorithm for convex hulls in two dimensions
• Maintenance of configurations in the plane
• Smoothsort, an alternative for sorting in situ
• An introduction to three algorithms for sorting in situ
• Small-dimensional linear programming and convex hulls made easy
• Stable minimum space partitioning in linear time
• Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
• In-place sorting with fewer moves
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Output-sensitive results on convex hulls, extreme points, and related problems
• Applications of random sampling in computational geometry. II
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Sorting a Random Access File in situ
• The Ultimate Planar Convex Hull Algorithm?
• Linear Programming in Linear Time When the Dimension Is Fixed
• Simplified stable merging tasks
• Stable Linear Time Sublinear Space Merging
• Unstable linear time O(1) space merging
• Convex hulls of finite sets of points in two and three dimensions
• A New Convex Hull Algorithm for Planar Sets
• An optimal real-time algorithm for planar convex hulls
• On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
• Enumerating extreme points in higher dimensions
• Programming as a Discipline of Mathematical Nature