The Ultimate Planar Convex Hull Algorithm?
From MaRDI portal
Publication:3718154
DOI10.1137/0215021zbMath0589.68035MaRDI QIDQ3718154
David G. Kirkpatrick, Raimund Seidel
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215021
68Q25: Analysis of algorithms and problem complexity
52-04: Software, source code, etc. for problems pertaining to convex and discrete geometry
52A10: Convex sets in (2) dimensions (including convex curves)
Related Items
An Output-Sensitive Convex Hull Algorithm for Planar Objects, Space-efficient planar convex hull algorithms, Output-sensitive peeling of convex and maximal layers, Randomized quickhull, Fast randomized parallel methods for planar convex hull construction, A lower bound for the integer element distinctness problem, Computing the convex hull in a hammock, Applications of a semi-dynamic convex hull algorithm, Geometric medians, An approximate algorithm for computing multidimensional convex hulls, An optimal convex hull algorithm in any fixed dimension, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Fast stabbing of boxes in high dimensions, Optimizing a constrained convex polygonal annulus, Constructing the convex hull of a partially sorted set of points, Optimal output-sensitive convex hull algorithms in two and three dimensions, Output-sensitive results on convex hulls, extreme points, and related problems, Staircase visibility and computation of kernels, Linear programming approaches to the convex hull problem in \(\mathbb{R}^ m\), A time-optimal parallel algorithm for three-dimensional convex hulls, Records, the maximal layer, and uniform distributions in monotone sets, Convex Hulls of Random Walks