An efficient algorithm for determining the convex hull of a finite planar set
From MaRDI portal
Publication:2552382
DOI10.1016/0020-0190(72)90045-2zbMath0236.68013OpenAlexW2025299767WikidataQ56017901 ScholiaQ56017901MaRDI QIDQ2552382
Publication date: 1972
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(72)90045-2
Related Items
Computing minimum length paths of a given homotopy class, Detection and computation of conservative kernels of models consisting of freeform curves and surfaces, using inequality constraints, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, Robust gift wrapping for the three-dimensional convex hull, Statistics of the maximum and the convex hull of a Brownian motion in confined geometries, Visual attractiveness in routing problems: a review, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Distribution-sensitive algorithms, Linear programming approaches to the convex hull problem in \(\mathbb{R}^ m\), Rearranging a sequence of points onto a line, Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times, Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments, A new active convex hull model for image regions, A time-optimal parallel algorithm for three-dimensional convex hulls, The convex hull of a set of convex polygons, Computing the Expected Value and Variance of Geometric Measures, ONLINE ROUTING IN CONVEX SUBDIVISIONS, PLANAR STRONG VISIBILITY, Culling a Set of Points for Roundness or Cylindricity Evaluations, COMPUTING THE CENTER OF AREA OF A CONVEX POLYGON, On random cartesian trees, On some geometric problems of color-spanning sets, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Linear Time Approximation Schemes for Geometric Maximum Coverage, Polygonal approximation of planar curves in theL1norm, Unnamed Item, Piece wise linear least–squares approximation of planar curves, Reliable Robust Path Planning with Application to Mobile Robots, Convex hull of planarh-polyhedra, ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE, An algorithm for the construction of convex hulls in simple integer recourse programming, The biobjective absolute center problem, \(\alpha\)-concave hull, a generalization of convex hull, Speed optimizations for liner networks with business constraints, Deconstructing approximate offsets, An algorithm reconstructing convex lattice sets., A new interface tracking method: the polygonal area mapping method, Triangular metric-based mesh adaptation for compressible multi-material flows in semi-Lagrangian coordinates, A dual approach for the continuous collapsing knapsack problem, Convex hulls of spheres and convex hulls of disjoint convex polytopes, On computing the convex hull of (piecewise) curved objects, Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation, Structural health monitoring of tall buildings with numerical integrator and convex-concave hull classification, A linear time combinatorial algorithm to compute the relative orthogonal convex hull of digital objects, Convex-hull algorithms: implementation, testing, and experimentation, A force-directed algorithm for drawing directed graphs symmetrically, Targeted influential nodes selection in location-aware social networks, A New Heuristic for Minimum Weight Triangulation, Improved subdivision scheme for the root computation of univariate polynomial equations, A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints, In quest of the Banks set in spatial voting games, An effective method to determine whether a point is within a convex hull and its generalized convex polyhedron classifier, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., Spiral Serpentine Polygonization of a Planar Point Set, Method of orienting curves for determining the convex hull of a finite set of points in the plane, On polyhedra induced by point sets in space, A new framework to relax composite functions in nonlinear programs, COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION, Multimesh finite element methods: solving PDEs on multiple intersecting meshes, A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set, Near-linear time approximation schemes for geometric maximum coverage, Implementation of Pellet's theorem, An Elementary Algorithm for Digital Arc Segmentation, Classroom examples of robustness problems in geometric computations, City-courier routing and scheduling problems, Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon, An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation, AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE, On finding the convex hull of a simple polygon, A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square, Comparative analysis of the computational geometry and neural network classification methods for person identification purposes via the EEG : Part 1, A new 2D tessellation for angle problems: the polar diagram, Progress on maximum weight triangulation, Determination of Q-convex sets by X-rays, O(n) algorithms for discrete n-point approximation by quasi-convex functions, Waste collection vehicle routing problem with time windows, Considering the attractor structure of chaotic maps for observer-based synchronization problems, EXACT AND OPTIMAL CONVEX HULLS IN 2D, A filtering technique for fast convex hull construction in \(\mathbb{R}^2\), Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots, QuickhullDisk: a faster convex hull algorithm for disks, Index-based, high-dimensional, cosine threshold querying with optimality guarantees, A new variational approach based on level-set function for convex hull problem with outliers, 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, Extremal convex polygons inscribed in a given convex polygon, Affine invariant triangulations, FLOATING-POINT ARITHMETIC FOR COMPUTATIONAL GEOMETRY PROBLEMS WITH UNCERTAIN DATA, Lower bounds for maximal and convex layers problems, On shortest three-edge-connected Steiner networks with Euclidean distance, Sensitivity analysis for 3D Maxwell's equations and its use in the resolution of an inverse medium problem at fixed frequency, On the identification of the convex hull of a finite set of points in the plane, Applications of a two-dimensional hidden-line algorithm to other geometric problems, Convex hull of a planar set of straight and circular line segments, Further steps on the reconstruction of convex polyominoes from orthogonal projections, On constant factors in comparison-based geometric algorithms and data structures, Quicker than Quickhull, A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning, Multidimensional global extremum seeking via the DIRECT optimisation algorithm, Efficient operations on discrete paths, Quasi-convex optimization, Generalized Delaunay triangulation for planar graphs, Invariants for time-series constraints, An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb{R}^n\), Finding transversals for sets of simple geometric figures, Extended reverse-convex programming: an approximate enumeration approach to global optimization, Compressing spatio-temporal trajectories, Graham triangulations and triangulations with a center are Hamiltonean, Polygonizations of point sets in the plane, An O(n) algorithm for least squares quasi-convex approximation, On determining the on-line minimax linear fit to a discrete point set in the plane, Geometric complexity of some location problems, Optimal convergence rate of the multitype sticky particle approximation of one-dimensional diagonal hyperbolic systems with monotonic initial data, Integrated QoS-aware resource management and scheduling with multi-resource constraints, Geometric problems on two-dimensional array processors, 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 parallel algorithms for computing convex hulls and for sorting, Space-efficient planar convex hull algorithms, Fastest-path planning for direction-dependent speed functions, Largest area convex hull of imprecise data based on axis-aligned squares, Optimal eviction policies for stochastic address traces, An O(n) algorithm for discrete n-point convex approximation with applications to continuous case, A linear algorithm for finding the convex hull of a simple polygon, Another efficient algorithm for convex hulls in two dimensions, Voronoi diagrams from convex hulls, On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination, A note on linear expected time algorithms for finding convex hulls, Minimizing makespan in an ordered flow shop with machine-dependent processing times, A note on finding convex hulls via maximal vectors, Average time behavior of distributive sorting algorithms, The design and analysis of a new hybrid sorting algorithm, An efficient convex hull algorithm using affine transformation in planar point set, Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering, How to reduce the average complexity of convex hull finding algorithms, Linear decision trees are too weak for convex hull problem, On the computer generation of random convex hulls, On the average complexity of some bucketing algorithms, A sublogarithmic convex hull algorithm, On the complexity of finding the convex hull of a set of points, Maintenance of configurations in the plane, A constant-time parallel algorithm for computing convex hulls, An efficient and numerically correct algorithm for the 2D convex hull problem, Container of (min,+)-linear systems, Augmenting the edge connectivity of planar straight line graphs to three, Numerical analyses of the boundary effect of radial basis functions in 3D surface reconstruction, Moment inequalities for random variables in computational geometry, The two variable per inequality abstract domain, Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays, Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays, Small-dimensional linear programming and convex hulls made easy, Computing the convex hull in a hammock, On steady state of continuous min-plus systems, The role of Steiner hulls in the solution to Steiner tree problems, Computing equilibria in discounted dynamic games, Max-plus singular values, Randomized quickhull, Fast randomized parallel methods for planar convex hull construction, Applications of a semi-dynamic convex hull algorithm, Hamiltonian triangulations and circumscribing polygons of disjoint line segments, Constructing strongly convex hulls using exact or rounded arithmetic, A linear-time algorithm to compute the triangular hull of a digital object, Well-separated pair decomposition in linear time?, The maximal distance between imprecise point objects, Inconstancy of finite and infinite sequences, Fast linear expected-time algorithms for computing maxima and convex hulls, Improved approximations for guarding 1.5-dimensional terrains, Approximating a real number by a rational number with a limited denominator: a geometric approach, Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees, Random convex hulls and extreme value statistics, Computing pseudotriangulations via branched coverings, Convex hull properties and algorithms, Computing simple circuits from a set of line segments, On computing approximate convex hulls, A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set, A more efficient convex hull algorithm, A characterization of nearest-neighbor rule decision surfaces and a new approach to generate them, Convex hull of a finite set of points in two dimensions, A fast convex hull algorithm, Divide and conquer for linear expected time, A simple algorithm for computing the smallest enclosing circle, Fast algorithms for the density finding problem, Empty pseudo-triangles in point sets, Highway hull revisited, A location-allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations, An approximate algorithm for computing multidimensional convex hulls, Automatic generating and spread of a plastic region in PIES, Linear time algorithms for convex and monotone approximation, Delaunay triangulation and the convex hull of n points in expected linear time, Numerical stability of a convex hull algorithm for simple polygons, A note on the expected time required to construct the outer layer, An optimal convex hull algorithm in any fixed dimension, Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set, Lipschitz condition in minimum norm problems on bounded functions, Some performance tests of convex hull algorithms, Some dynamic computational geometry problems, Iterative learning control based on extremum seeking, A workbench for computational geometry, The two-line center problem from a polar view: a new algorithm and data structure, The Persistent Homology of Cyclic Graphs, Tractable Relaxations of Composite Functions, A quantum search algorithm of two-dimensional convex hull, Holistic fleet optimization incorporating system design considerations, Solving the prize‐collecting Euclidean Steiner tree problem, Convex geometry of finite exchangeable laws and de Finetti style representation with universal correlated corrections, Efficient Optimization of Partition Scan Statistics via the Consecutive Partitions Property, Dynamic convex hulls under window-sliding updates, Optimal Switching Sequence for Switched Linear Systems, Proper colorability of segment intersection graphs, Cargo transport properties are enhanced by cylindrical microtubule geometry and elliptical contact zone on cargo surface, A tabu search with geometry‐based sparsification methods for angular traveling salesman problems, Area and perimeter covered by anomalous diffusion processes, A consistent semantics of self-adjusting computation, The complexity of linear programming, Applications of a semi-dynamic convex hull algorithm, Unnamed Item, Unnamed Item, Continuous Center Problems, Tropical Roots as Approximations to Eigenvalues of Matrix Polynomials, An Exact Algorithm for Minimizing a Sum of Euclidean Norms on Rays in 2D and 3D
Cites Work
