Finding the convex hull of a simple polygon

DOI10.1016/0196-6774(83)90013-5zbMATH Open0532.68072OpenAlexW1964869106WikidataQ106189157 ScholiaQ106189157MaRDI QIDQ5896232FDOQ5896232

Ron 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

Recommendations

• On finding the convex hull of a simple polygon
• Finding the convex hull of a simple polygon in linear time
• Finding the convex hull facet by facet
• A convex hull algorithm for planar simple polygons
• scientific article; zbMATH DE number 522850
• The convex hull of a set of convex polygons
• scientific article; zbMATH DE number 4045150
• scientific article; zbMATH DE number 742638
• scientific article
• Finding Extremal Polygons

zbMATH Keywords

convex hullcomputer graphicslinear-time algorithmsimple polygon

Mathematics Subject Classification ID

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

Cited In (56)

• A lower bound on the complexity of the convex hull problem for simple polyhedra
• Optimal computation of finitely oriented convex hulls
• tigers
• COMPUTING THE CENTER OF AREA OF A CONVEX POLYGON
• Staircase visibility and computation of kernels
• Root radii and subdivision for polynomial root-finding
• A linear algorithm for eliminating hidden-lines from a polygonal cylinder
• Title not available (Why is that?)
• Convex hulls of objects bounded by algebraic curves
• On determining the on-line minimax linear fit to a discrete point set in the plane
• Finding the convex hull of a simple polygon in linear time
• An efficient algorithm for finding the CSG representation of a simple polygon
• Convex hulls of piecewise-smooth Jordan curves
• Title not available (Why is that?)
• Generalized Delaunay triangulation for planar graphs
• Multilevel Monte Carlo front-tracking for random scalar conservation laws
• Robust explicit estimators using the power-weighted repeated medians
• Constructing the convex hull of a partially sorted set of points
• 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
• Algorithms for subpath convex hull queries and ray-shooting among segments
• THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS
• On finding the convex hull of a simple polygon
• Fast evaluation and root finding for polynomials with floating-point coefficients
• Fast evaluation and root finding for polynomials with floating-point coefficients
• Numerical stability of a convex hull algorithm for simple polygons
• Title not available (Why is that?)
• A linear time algorithm for finding all farthest neighbors in a convex polygon
• On-line construction of the convex hull of a simple polyline
• A simple algorithm for computing the smallest enclosing circle
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• A linear time algorithm to remove winding of a simple polygon
• A new elementary geometric approach to option pricing bounds in discrete time models
• EXACT AND OPTIMAL CONVEX HULLS IN 2D
• The order of points on the second convex hull of a simple polygon
• Three problems about simple polygons
• Title not available (Why is that?)
• Setting defect charts control limits to balance cycle time and yield for a tandem production line
• Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
• Computing external farthest neighbors for a simple polygon
• Title not available (Why is that?)
• Computational geometry in a curved world
• Fast skeleton construction
• Continuous Center Problems
• The Ultimate Planar Convex Hull Algorithm?
• Lipschitz condition in minimum norm problems on bounded functions
• An optimal algorithm for computing a minimum nested nonconvex polygon
• COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET
• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• The Bohnenblust-Spitzer algorithm and its applications
• Title not available (Why is that?)
• On computing the closest boundary point on the convex hull
• Optimal time bounds for some proximity problems in the plane
• COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896232)