Finding the convex hull of a simple polygon

DOI10.1016/0196-6774(83)90013-5zbMath0532.68072OpenAlexW1964869106WikidataQ106189157 ScholiaQ106189157MaRDI QIDQ5896232

Ronald L. Graham, F. Frances Yao

Publication date: 1983

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(83)90013-5

zbMATH Keywords

computer graphicsconvex hulllinear-time algorithmsimple polygon

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Polyhedra and polytopes; regular figures, division of spaces (51M20) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)

Related Items (37)

Generalized Delaunay triangulation for planar graphs ⋮ Multilevel Monte Carlo front-tracking for random scalar conservation laws ⋮ Root radii and subdivision for polynomial root-finding ⋮ Finding the convex hull of a simple polygon in linear time ⋮ Staircase visibility and computation of kernels ⋮ A new elementary geometric approach to option pricing bounds in discrete time models ⋮ A linear algorithm for eliminating hidden-lines from a polygonal cylinder ⋮ Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons ⋮ Setting defect charts control limits to balance cycle time and yield for a tandem production line ⋮ On-line construction of the convex hull of a simple polyline ⋮ A lower bound on the complexity of the convex hull problem for simple polyhedra ⋮ tigers ⋮ A linear time algorithm for finding all farthest neighbors in a convex polygon ⋮ Fast evaluation and root finding for polynomials with floating-point coefficients ⋮ Fast skeleton construction ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Three problems about simple polygons ⋮ Computational geometry in a curved world ⋮ An optimal algorithm for computing a minimum nested nonconvex polygon ⋮ Computing external farthest neighbors for a simple polygon ⋮ Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds ⋮ Method of orienting curves for determining the convex hull of a finite set of points in the plane ⋮ COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION ⋮ THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS ⋮ Optimal time bounds for some proximity problems in the plane ⋮ Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon ⋮ On finding the convex hull of a simple polygon ⋮ Constructing the convex hull of a partially sorted set of points ⋮ An efficient algorithm for finding the CSG representation of a simple polygon ⋮ Optimal computation of finitely oriented convex hulls ⋮ Continuous Center Problems ⋮ Numerical stability of a convex hull algorithm for simple polygons ⋮ Convex hulls of objects bounded by algebraic curves ⋮ Lipschitz condition in minimum norm problems on bounded functions ⋮ An Output-Sensitive Convex Hull Algorithm for Planar Objects ⋮ COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET ⋮ The Bohnenblust-Spitzer algorithm and its applications

This page was built for publication: Finding the convex hull of a simple polygon