Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time

DOI10.1016/J.COMGEO.2005.11.005MaRDI QIDQ2489016zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Hervé Brönnimann

Publication date 16 May 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2005.11.005

zbMATH Keywords

Computational geometryConvex hullsimple polygonal lineSpace-efficient algorithm

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• LATIN 2004: Theoretical Informatics
• Space-efficient planar convex hull algorithms
• Finding the convex hull of a simple polygon in linear time
• Finding the convex hull of a simple polygon
• On finding the convex hull of a simple polygon

Cites work

• scientific article; zbMATH DE number 1220053 (Why is no real title available?)
• Asymptotically efficient in-place merging
• Introduction to algorithms
• On finding the convex hull of a simple polygon
• On-line construction of the convex hull of a simple polyline
• Sorting multisets stably in minimum space
• Space-efficient planar convex hull algorithms
• Stable in situ sorting and minimum data movement
• Stable minimum space partitioning in linear time
• Towards in-place geometric algorithms and data structures

Cited in

(21)

• Space-efficient planar convex hull algorithms
• A new algorithm for computing the convex hull of a planar point set
• LATIN 2004: Theoretical Informatics
• A linear-time algorithm for solving the strong hidden-line problem in a simple polygon
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Cartographic line simplification and polygon CSG formulae in O(n^* n) time
• Memory-constrained algorithms for simple polygons
• scientific article; zbMATH DE number 6846375 (Why is no real title available?)
• Optimal time-space tradeoff for the 2D convex-hull problem
• In-place algorithms for computing (Layers of) maxima
• Covering paths for planar point sets
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• scientific article; zbMATH DE number 2089211 (Why is no real title available?)
• Space efficient linear time algorithms for BFS, DFS and applications
• Simplified linear-time Jordan sorting and polygon clipping
• scientific article; zbMATH DE number 2086251 (Why is no real title available?)
• Space-time trade-offs for stack-based algorithms
• An algorithm to find the lineality space of the positive hull of a set of vectors
• Reprint of: Memory-constrained algorithms for simple polygons
• A linear-time algorithm to compute the triangular hull of a digital object
• Memory efficient algorithms for cactus graphs and block graphs

This page was built for publication: Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time

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