Optimal output-sensitive convex hull algorithms in two and three dimensions
From MaRDI portal
Publication:1816462
DOI10.1007/BF02712873zbMath0857.68111WikidataQ60059802 ScholiaQ60059802MaRDI QIDQ1816462
Publication date: 26 November 1996
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)
Related Items
Efficient operations on discrete paths ⋮ An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb{R}^n\) ⋮ Robust vertex enumeration for convex hulls in high dimensions ⋮ Skyline Computation with Noisy Comparisons ⋮ New variants of perfect non-crossing matchings ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ In-place algorithms for computing (Layers of) maxima ⋮ Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments ⋮ Semidual Regularized Optimal Transport ⋮ Extreme point and halving edge search in abstract order types ⋮ Space-efficient planar convex hull algorithms ⋮ ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ Reprint of: Extreme point and halving edge search in abstract order types ⋮ Faster output-sensitive skyline computation algorithm ⋮ A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff ⋮ Randomized approximation scheme for Steiner multi cycle in the Euclidean plane ⋮ Recursive voids for identifying a nonconvex boundary of a set of points in the plane ⋮ Dynamic convex hulls under window-sliding updates ⋮ An efficient convex hull algorithm using affine transformation in planar point set ⋮ Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane ⋮ Convex hulls of spheres and convex hulls of disjoint convex polytopes ⋮ Efficiently testing digital convexity and recognizing digital convex polygons ⋮ Shortest paths and convex hulls in 2D complexes with non-positive curvature ⋮ A linear time combinatorial algorithm to compute the relative orthogonal convex hull of digital objects ⋮ Convex-hull algorithms: implementation, testing, and experimentation ⋮ Connectivity guarantees for wireless networks with directional antennas ⋮ An effective method to determine whether a point is within a convex hull and its generalized convex polyhedron classifier ⋮ A new framework to relax composite functions in nonlinear programs ⋮ Planar lower envelope of monotone polygonal chains ⋮ New variants of perfect non-crossing matchings ⋮ Hausdorff approximation of 3D convex polytopes ⋮ Approximating a real number by a rational number with a limited denominator: a geometric approach ⋮ Convex Hulls on Cellular Automata ⋮ Techniques and Open Questions in Computational Convex Analysis ⋮ Optimizing a constrained convex polygonal annulus ⋮ Computing pseudotriangulations via branched coverings ⋮ Convex hull properties and algorithms ⋮ Unnamed Item ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection ⋮ A filtering technique for fast convex hull construction in \(\mathbb{R}^2\) ⋮ The Complex Version of the Minimum Support Criterion ⋮ QuickhullDisk: a faster convex hull algorithm for disks ⋮ A new variational approach based on level-set function for convex hull problem with outliers ⋮ A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation ⋮ Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance ⋮ An alternative definition for digital convexity ⋮ An alternative definition for digital convexity ⋮ Maximizing dominance in the plane and its applications ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Efficient Algorithms to Test Digital Convexity ⋮ An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem ⋮ Linear-Time Convexity Test for Low-Order Piecewise Polynomials ⋮ Linear time approximation of 3D convex polytopes ⋮ On constant factors in comparison-based geometric algorithms and data structures ⋮ Quicker than Quickhull
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding the upper envelope of n line segments in O(n log n) time
- Fast detection of polyhedral intersection
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Derandomizing an output-sensitive convex hull algorithm in 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
- An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
- A new linear algorithm for intersecting convex polygons
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Finding the convex hull facet by facet
- The Ultimate Planar Convex Hull Algorithm?
- An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
- Convex hulls of finite sets of points in two and three dimensions
- An Algorithm for Convex Polytopes
