An optimal convex hull algorithm in any fixed dimension

DOI10.1007/BF02573985zbMath0786.68091WikidataQ56070314 ScholiaQ56070314MaRDI QIDQ1312190

Publication date: 15 May 1994

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131280

zbMATH Keywords

convex hull Voronoi diagram computational geometry derandomizing-technique Raghavan-Spencer method random-looking permutations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

Valuations in Image Analysis, Efficient operations on discrete paths, On statistical learning of simplices: unmixing problem revisited, Robust vertex enumeration for convex hulls in high dimensions, The minimum convex container of two convex polytopes under translations, A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes, Efficient algorithm for simulating particles in true quasiperiodic environments, On physics-informed data-driven isotropic and anisotropic constitutive models through probabilistic machine learning and space-filling sampling, A largest empty hypersphere metaheuristic for robust optimisation with implementation uncertainty, Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology, Analysis of Complex and Heterogeneous Data Using FCA and Monadic Predicates, An introduction to randomization in computational geometry, Equilibrium computation of the Hart and Mas-Colell bargaining model, How good are convex hull algorithms?, Convex hulls, oracles, and homology, APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS, Almost optimal set covers in finite VC-dimension, Bounds on the complexity of halfspace intersections when the bounded faces have small dimension, Computing convex hulls and counting integer points with \texttt{polymake}, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, An algorithm for constructing the convex hull of a set of spheres in dimension \(d\), An algorithm for canonical forms of finite subsets of \(\mathbb {Z}^d\) up to affinities, Topological relations between separating circles, Skew Jensen-Bregman Voronoi Diagrams, Holistic fleet optimization incorporating system design considerations, Uniform behaviors of random polytopes under the Hausdorff metric, Automorphism groups of hyperbolic lattices, OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS, Unnamed Item, How to build high quality L2R training data: unsupervised compression-based selective sampling for learning to rank, Polynomial Bell Inequalities, Finding largest rectangles in convex polygons, Sufficient condition for injectivity of NURBS volumes by tangent cones, Minimizing the error of linear separators on linearly inseparable data, Graph problems arising from parameter identification of discrete dynamical systems, Convex hulls of spheres and convex hulls of disjoint convex polytopes, Shortest paths and convex hulls in 2D complexes with non-positive curvature, \textsc{NextPriorityConcept}: a new and generic algorithm computing concepts from complex and heterogeneous data, Manifold reconstruction using tangential Delaunay complexes, Polar degrees and closest points in codimension two, An effective method to determine whether a point is within a convex hull and its generalized convex polyhedron classifier, Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling, The number of cylindrical shells, Methods for estimation of convex sets, Rigorous cubical approximation and persistent homology of continuous functions, On the Computational Complexity of Linear Discrepancy, A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes, A general solution for robust linear programs with distortion risk constraints, Concentration of the empirical level sets of Tukey's halfspace depth, Voronoi-based estimation of Minkowski tensors from finite point samples, A linear-time algorithm to compute the triangular hull of a digital object, CONFORMAL GEOMETRY OF ESCORT PROBABILITY AND ITS APPLICATIONS, Cutting hyperplanes for divide-and-conquer, Monotone and consistent discretization of the Monge-Ampère operator, A complete description of cones and polytopes including hypervolumes of all facets of a polytope, Unnamed Item, RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS, Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball, Ellipsoidal one-class constraint acquisition for quadratically constrained programming, Bregman Voronoi diagrams, Estimation of convex supports from noisy measurements, An alternative definition for digital convexity, Nonlocality in many-body quantum systems detected with two-body correlators, Constructing the convex hull of a partially sorted set of points, An alternative definition for digital convexity, Conformal Flattening on the Probability Simplex and Its Applications to Voronoi Partitions and Centroids, On overlays and minimization diagrams, SUPERIMPOSING VORONOI COMPLEXES FOR SHAPE DEFORMATION, Generating all vertices of a polyhedron is hard, COMPUTING CONVEX HULLS BY AUTOMATA ITERATION, Efficient Algorithms to Test Digital Convexity, An approximate algorithm for computing multidimensional convex hulls, A characterization theorem and an algorithm for a convex hull problem, Optimal Algorithm for Solution of Discrete Convex Combinations Problem, Estimating the number of vertices of a polyhedron, Voronoi Diagrams of Moving Points, Dynamic maintenance and visualization of molecular surfaces., The symplectic geometry of closed equilateral random walks in 3-space

Cites Work