Space-efficient planar convex hull algorithms
DOI10.1016/J.TCS.2003.05.004zbMATH Open1068.68153DBLPjournals/tcs/BronnimannIKMMT04OpenAlexW1973037646WikidataQ57009423 ScholiaQ57009423MaRDI QIDQ596137FDOQ596137
Pat Morin, Jason Morrison, Hervé Brönnimann, Godfried Toussaint, Jyrki Katajainen, John Iacono
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) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)
Cites Work
- An efficient algorithm for determining the convex hull of a finite planar set
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Applications of random sampling in computational geometry. II
- Title not available (Why is that?)
- Linear Programming in Linear Time When the Dimension Is Fixed
- Another efficient algorithm for convex hulls in two dimensions
- A New Convex Hull Algorithm for Planar Sets
- Maintenance of configurations in the plane
- Programming as a Discipline of Mathematical Nature
- The Ultimate Planar Convex Hull Algorithm?
- On the identification of the convex hull of a finite set of points in the plane
- Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
- Output-sensitive results on convex hulls, extreme points, and related problems
- Convex hulls of finite sets of points in two and three dimensions
- Enumerating extreme points in higher dimensions
- Small-dimensional linear programming and convex hulls made easy
- An optimal real-time algorithm for planar convex hulls
- Smoothsort, an alternative for sorting in situ
- An introduction to three algorithms for sorting in situ
- Stable minimum space partitioning in linear time
- In-place sorting with fewer moves
- Sorting a Random Access File in situ
- Simplified stable merging tasks
- Title not available (Why is that?)
- Stable Linear Time Sublinear Space Merging
- Unstable linear time O(1) space merging
- On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
- Randomized quickhull
- Stable in situ sorting and minimum data movement
Cited In (18)
- A new algorithm for computing the convex hull of a planar point set
- LATIN 2004: Theoretical Informatics
- Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
- Memory-constrained algorithms for simple polygons
- An in-place algorithm for Klee's measure problem in two dimensions
- An efficient convex hull algorithm using affine transformation in planar point set
- In-place algorithms for computing (Layers of) maxima
- Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
- Line-segment intersection made in-place
- Synergistic solutions for merging and computing planar convex hulls
- Prune-and-search with limited workspace
- Convex hull properties and algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new active convex hull model for image regions
- Convex-hull algorithms: implementation, testing, and experimentation
- Minimum Dominating Set Problem for Unit Disks Revisited
- Reprint of: Memory-constrained algorithms for simple polygons
Uses Software
Recommendations
This page was built for publication: Space-efficient planar convex hull algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596137)
