The Ultimate Planar Convex Hull Algorithm?
From MaRDI portal
Publication:3718154
DOI10.1137/0215021zbMath0589.68035OpenAlexW1976915153MaRDI QIDQ3718154
Raimund Seidel, David G. Kirkpatrick
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
Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10)
Related Items
An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb{R}^n\), Records, the maximal layer, and uniform distributions in monotone sets, Geometric containment and vector dominance, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Distribution-sensitive algorithms, A variant of Ben-Or's lower bound for algebraic decision trees, Staircase visibility and computation of kernels, Linear programming approaches to the convex hull problem in \(\mathbb{R}^ m\), Some problems in computational geometry, A new active convex hull model for image regions, A time-optimal parallel algorithm for three-dimensional convex hulls, Finding the convex hull of a sorted point set in parallel, Extreme point and halving edge search in abstract order types, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Optimal parallel algorithms for computing convex hulls and for sorting, Space-efficient planar convex hull algorithms, An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains, Reprint of: Extreme point and halving edge search in abstract order types, Dynamic convex hulls under window-sliding updates, Proper colorability of segment intersection graphs, Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set, Convex hulls of spheres and convex hulls of disjoint convex polytopes, Efficiently testing digital convexity and recognizing digital convex polygons, On computing the convex hull of (piecewise) curved objects, Bottleneck convex subsets: finding \(k\) large convex sets in a point set, Shortest paths and convex hulls in 2D complexes with non-positive curvature, Computing Euclidean maximum spanning trees, An optimal parallel algorithm for linear programming in the plane, Convex-hull algorithms: implementation, testing, and experimentation, An efficient and numerically correct algorithm for the 2D convex hull problem, Connectivity guarantees for wireless networks with directional antennas, A new algorithm for computing the convex hull of a planar point set, Prune-and-search with limited workspace, A lower bound for the integer element distinctness problem, Computing the convex hull in a hammock, Output-sensitive peeling of convex and maximal layers, Adaptive searching in succinctly encoded binary relations and tree-structured documents, Randomized quickhull, Fast randomized parallel methods for planar convex hull construction, Applications of a semi-dynamic convex hull algorithm, Geometric medians, Covering points with a polygon, A linear-time algorithm to compute the triangular hull of a digital object, Random convex hulls and extreme value statistics, A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square, Convex Hulls on Cellular Automata, Optimizing a constrained convex polygonal annulus, Computing pseudotriangulations via branched coverings, Applications of a semi-dynamic convex hull algorithm, Unnamed Item, Computing simple circuits from a set of line segments, A filtering technique for fast convex hull construction in \(\mathbb{R}^2\), QuickhullDisk: a faster convex hull algorithm for disks, A new variational approach based on level-set function for convex hull problem with outliers, Convex Hulls of Random Walks, Paths with no Small Angles, 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, Computing shortest transversals, Opportunistic algorithms for eliminating supersets, Selection Algorithms with Small Groups, Applications of random sampling in computational geometry. II, On computing the closest boundary point on the convex hull, Lower bounds for maximal and convex layers problems, Efficient Algorithms to Test Digital Convexity, An approximate algorithm for computing multidimensional convex hulls, Fast stabbing of boxes in high dimensions, An optimal convex hull algorithm in any fixed dimension, On constant factors in comparison-based geometric algorithms and data structures, On partitions and presortedness of sequences, An Output-Sensitive Convex Hull Algorithm for Planar Objects, Quicker than Quickhull
