Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
From MaRDI portal
Publication:2489016
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
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