Convex hull of a finite set of points in two dimensions

DOI10.1016/0020-0190(78)90021-2zbMath0392.52002OpenAlexW2075232087MaRDI QIDQ1251803

A. Bykat

Publication date: 1978

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(78)90021-2

zbMATH Keywords

Algorithm For Determination of the Convex HullConvex Hull of a Finite Set of Points in Two Dimensions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10) Algorithms in computer science (68W99)

Related Items

Quasi-convex optimization ⋮ An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in \(\mathbb{R}^n\) ⋮ A new point creation scheme for uniform Delaunay triangulation ⋮ Finding the convex hull of a simple polygon in linear time ⋮ On determining the on-line minimax linear fit to a discrete point set in the plane ⋮ Graphical exploration of the weight space in three-objective mixed integer linear programs ⋮ Three-dimensional unstructured mesh generation. I: Fundamental aspects of triangulation and point creation ⋮ A fast and efficient algorithm for determining the connected orthogonal convex hulls ⋮ A linear algorithm for finding the convex hull of a simple polygon ⋮ Another efficient algorithm for convex hulls in two dimensions ⋮ Further comments on Bykat's convex hull algorithm ⋮ Convex-hull algorithms: implementation, testing, and experimentation ⋮ Computing the convex hull in a hammock ⋮ Comments on convex hull of a finite set of points in two dimensions ⋮ Randomized quickhull ⋮ Comments on convex hull of a finite set of points in two dimensions ⋮ On finding the convex hull of a simple polygon ⋮ A filtering technique for fast convex hull construction in \(\mathbb{R}^2\) ⋮ QuickhullDisk: a faster convex hull algorithm for disks ⋮ Multi-core Implementations of Geometric Algorithms ⋮ Lipschitz condition in minimum norm problems on bounded functions ⋮ Some performance tests of convex hull algorithms ⋮ Quicker than Quickhull

Cites Work

• A more efficient convex hull algorithm
• 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
• Determining the Three-dimensional Convex Hull of a Polyhedron
• Measuring Concavity on a Rectangular Mosaic