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

DOI10.1016/j.comgeo.2005.11.005zbMath1089.65014MaRDI QIDQ2489016

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 geometry; Convex hull; simple polygonal line; Space-efficient algorithm

Mathematics Subject Classification ID

52B55: Computational aspects related to convexity

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

Reprint of: Memory-constrained algorithms for simple polygons, Space-time trade-offs for stack-based algorithms, Memory efficient algorithms for cactus graphs and block graphs, In-place algorithms for computing (Layers of) maxima, A new algorithm for computing the convex hull of a planar point set, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, Covering paths for planar point sets, Space efficient linear time algorithms for BFS, DFS and applications, Memory-constrained algorithms for simple polygons, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits

Cites Work

• Unnamed Item
• Unnamed Item
• Space-efficient planar convex hull algorithms
• Stable in situ sorting and minimum data movement
• On-line construction of the convex hull of a simple polyline
• Stable minimum space partitioning in linear time
• On finding the convex hull of a simple polygon
• Sorting multisets stably in minimum space
• Towards in-place geometric algorithms and data structures
• Asymptotically efficient in-place merging