Space-efficient planar convex hull algorithms
From MaRDI portal
Publication:596137
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
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
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
