Convex hulls of finite sets of points in two and three dimensions

DOI10.1145/359423.359430zbMath0342.68030OpenAlexW2041775009MaRDI QIDQ4110607

Publication date: 1977

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/359423.359430

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Pattern recognition, speech recognition (68T10) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology, Distribution-sensitive algorithms, The Persistent Homology of Cyclic Graphs, New parallel algorithms for convex hull and triangulation in 3-dimensional space, Separating a polyhedron by one translation from a set of obstacles, Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations, Comments on convex hull of a finite set of points in two dimensions, A new duality result concerning Voronoi diagrams, The complexity of linear programming, An efficient algorithm for the three-dimensional diameter problem, Unnamed Item, Evaluation of sphericity error from coordinate measurement data using computational geometric techniques, Efficient Algorithms to Test Digital Convexity, Quasi-convex optimization, Computing circular separability, Voronoi diagrams and arrangements, Finding minimal enclosing boxes, Finding transversals for sets of simple geometric figures, Orthogonal weightet linear $L_ 1$ and $L_ \infty$ approximation and applications, Robust gift wrapping for the three-dimensional convex hull, Computing minimum-area rectilinear convex hull and $L$-shape, Edge-skeletons in arrangements with applications, Polygonizations of point sets in the plane, Geometric containment and vector dominance, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Linear programming approaches to the convex hull problem in $\mathbb{R}^ m$, Computing depth contours of bivariate point clouds, On determining the on-line minimax linear fit to a discrete point set in the plane, Geometric complexity of some location problems, On the two-dimensional Davenport-Schinzel problem, Tetrahedrizing point sets in three dimensions, A time-optimal parallel algorithm for three-dimensional convex hulls, The convex hull of a set of convex polygons, Parallel algorithms for some functions of two convex polygons, A new O(n$\cdot \log \,n)$ algorithm for computing the intersection of convex polygons, A lower bound on the complexity of the convex hull problem for simple polyhedra, Finding the convex hull of a sorted point set in parallel, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Parallel computational geometry, Optimal parallel algorithms for computing convex hulls and for sorting, ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE, Space-efficient planar convex hull algorithms, Parallel construction of subdivision hierarchies, $\alpha$-concave hull, a generalization of convex hull, Approximating spheres and sphere patches, An O(n) algorithm for discrete n-point convex approximation with applications to continuous case, Another efficient algorithm for convex hulls in two dimensions, Voronoi diagrams from convex hulls, A new implementation of the geometric method for solving the Eady slice equations, On the $\Omega (n\log n)$ lower bound for convex hull and maximal vector determination, A note on finding convex hulls via maximal vectors, Self-stabilizing gathering with strong multiplicity detection, How to reduce the average complexity of convex hull finding algorithms, A dual approach for the continuous collapsing knapsack problem, Convex hulls of spheres and convex hulls of disjoint convex polytopes, Efficiently testing digital convexity and recognizing digital convex polygons, Maintenance of configurations in the plane, Structural health monitoring of tall buildings with numerical integrator and convex-concave hull classification, An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane, The two variable per inequality abstract domain, Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays, Small-dimensional linear programming and convex hulls made easy, Computing the convex hull in a hammock, Bisections and ham-sandwich cuts of convex polygons and polyhedra, LR-visibility in polygons, The $\gamma$-neighborhood graph, Fuzzy clustering using the convex hull as geometrical model, Outlier respecting points approximation, Geometric medians, Mathematical morphological operations of boundary-represented geometric objects., Hausdorff approximation of 3D convex polytopes, Inconstancy of finite and infinite sequences, Fast linear expected-time algorithms for computing maxima and convex hulls, A comparison of sequential Delaunay triangulation algorithms., Random convex hulls and extreme value statistics, On finding the convex hull of a simple polygon, On the randomized construction of the Delaunay tree, O(n) algorithms for discrete n-point approximation by quasi-convex functions, A simple algorithm for building the 3-D convex hull, Convex hull properties and algorithms, Maintaining multiple representations of dynamic data structures, On computing approximate convex hulls, 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$, Extended box clustering for classification problems, A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set, A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions, QuickhullDisk: a faster convex hull algorithm for disks, Modélisation et optimisation numérique pour la reconstruction d'un polyèdre à partir de son image gaussienne généralisée, A new variational approach based on level-set function for convex hull problem with outliers, A fast convex hull algorithm, Two algorithms for constructing a Delaunay triangulation, Finding the intersection of two convex polyhedra, Representing geometric structures in $d$ dimensions: Topology and order, Divide and conquer for linear expected time, Finding the intersection of n half-spaces in time O(n log n), Optimal output-sensitive convex hull algorithms in two and three dimensions, Output-sensitive results on convex hulls, extreme points, and related problems, Triangulating point sets in space, Optimal algorithms for symmetry detection in two and three dimensions, Top tree compression of tries, Applications of random sampling in computational geometry. II, Lower bounds for maximal and convex layers problems, An approximate algorithm for computing multidimensional convex hulls, Linear time algorithms for convex and monotone approximation, An n log n algorithm for determining the congruity of polyhedra, A note on the expected time required to construct the outer layer, An optimal convex hull algorithm in any fixed dimension, Triangulation automatique d’un polyèdre en dimension $N$, Linear time approximation of 3D convex polytopes, Lipschitz condition in minimum norm problems on bounded functions, Finding extreme points in three dimensions and solving the post-office problem in the plane, Some dynamic computational geometry problems