On-line construction of the convex hull of a simple polyline
From MaRDI portal
Publication:1107996
DOI10.1016/0020-0190(87)90086-XzbMath0653.68028MaRDI QIDQ1107996
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)
Related Items (41)
Lyndon + Christoffel = digitally convex ⋮ Tangential cover for thick digital curves ⋮ Filling polyhedral molds ⋮ Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ A simple algorithm for digital line recognition in the general case ⋮ Optimizing Squares Covering a Set of Points ⋮ Cartographic line simplication and polygon CSG formulae in O(n log* n) time ⋮ Dynamic convex hulls under window-sliding updates ⋮ Optimal Area Polygonization by Triangulation and Visibility Search ⋮ Efficient observer-dependent simplification in polygonal domains ⋮ Three problems about simple polygons ⋮ On computing the convex hull of (piecewise) curved objects ⋮ A linear time combinatorial algorithm to compute the relative orthogonal convex hull of digital objects ⋮ Unnamed Item ⋮ Geometric preservation of 2D digital objects under rigid motions ⋮ A new algorithm for computing the convex hull of a planar point set ⋮ A simple algorithm for determining the envelope of a set of lines ⋮ COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION ⋮ Attraction-convexity and normal visibility ⋮ Optimal simplification of polygonal chains for subpixel-accurate rendering ⋮ Optimizing squares covering a set of points ⋮ Covering paths for planar point sets ⋮ The Erdős--Nagy theorem and its ramifications ⋮ Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time ⋮ Triangulating input-constrained planar point sets ⋮ Polygons cuttable by a circular saw ⋮ Measure of circularity for parts of digital boundaries and its fast computation ⋮ Tangential Cover for Thick Digital Curves ⋮ Optimizing generalized kernels of polygons ⋮ An efficient algorithm for finding the CSG representation of a simple polygon ⋮ Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time ⋮ Two linear-time algorithms for computing the minimum length polygon of a digital contour ⋮ Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour ⋮ Parameter identification of 1D fractal interpolation functions using bounding volumes ⋮ Stabbing information of a simple polygon ⋮ Optimal placement of base stations in border surveillance using limited capacity drones ⋮ Linear segmentation of discrete curves into blurred segments ⋮ Adaptive Planar Point Location ⋮ Numerical stability of a convex hull algorithm for simple polygons ⋮ GEODESIC-PRESERVING POLYGON SIMPLIFICATION ⋮ A workbench for computational geometry
Cites Work
This page was built for publication: On-line construction of the convex hull of a simple polyline
