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.68013DBLPjournals/ipl/Graham72OpenAlexW2025299767WikidataQ56017901 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 (only showing first 100 items - show all)
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 ⋮ 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 ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ 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
Cites Work
This page was built for publication: An efficient algorithm for determining the convex hull of a finite planar set
