A linear algorithm for finding the convex hull of a simple polygon
From MaRDI portal
Publication:1134524
DOI10.1016/0020-0190(79)90069-3zbMath0423.68031OpenAlexW2056531186MaRDI QIDQ1134524
Publication date: 1979
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(79)90069-3
Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)
Related Items
Generalized Delaunay triangulation for planar graphs, Finding the convex hull of a simple polygon in linear time, Staircase visibility and computation of kernels, Filling polyhedral molds, A linear algorithm for eliminating hidden-lines from a polygonal cylinder, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, PLANAR STRONG VISIBILITY, 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, On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination, Three problems about simple polygons, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Some chain visibility problems in a simple polygon, Augmenting the edge connectivity of planar straight line graphs to three, A new algorithm for computing the convex hull of a planar point set, COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION, Optimal time bounds for some proximity problems in the plane, On finding the convex hull of a simple polygon, The Erdős--Nagy theorem and its ramifications, Approximate convex decomposition of polygons, Guarding Exterior Region of a Simple Polygon, Optimizing generalized kernels of polygons, An efficient algorithm for finding the CSG representation of a simple polygon, Optimal computation of finitely oriented convex hulls, On separating two simple polygons by a single translation, Applications of a two-dimensional hidden-line algorithm to other geometric problems, The symmetric all-furthest-neighbor problem, A linear time algorithm for computing the convex hull of an ordered crossing polygon, On the conditions for success of Sklansky's convex hull algorithm, A linear time algorithm for obtaining the convex hull of a simple polygon, Efficient splitting and merging algorithms for order decomposable problems., A convex hull algorithm for planar simple polygons, Numerical stability of a convex hull algorithm for simple polygons, Convex hulls of objects bounded by algebraic curves, An Output-Sensitive Convex Hull Algorithm for Planar Objects
Cites Work
