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

DOI10.1016/J.COMGEO.2005.11.005zbMATH Open1089.65014OpenAlexW2065822517MaRDI QIDQ2489016FDOQ2489016

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

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

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)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• Towards in-place geometric algorithms and data structures
• Space-efficient planar convex hull algorithms
• On finding the convex hull of a simple polygon
• Stable minimum space partitioning in linear time
• Stable in situ sorting and minimum data movement
• On-line construction of the convex hull of a simple polyline
• Asymptotically efficient in-place merging
• Sorting multisets stably in minimum space

Cited In (21)

• A new algorithm for computing the convex hull of a planar point set
• Space-efficient planar convex hull algorithms
• 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\log^* n)\) time
• Title not available (Why is that?)
• Memory-constrained algorithms for simple polygons
• 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
• Title not available (Why is that?)
• Space efficient linear time algorithms for BFS, DFS and applications
• Simplified linear-time Jordan sorting and polygon clipping
• Title not available (Why is that?)
• Space-time trade-offs for stack-based algorithms
• An algorithm to find the lineality space of the positive hull of a set of vectors
• A linear-time algorithm to compute the triangular hull of a digital object
• Memory efficient algorithms for cactus graphs and block graphs
• Reprint of: Memory-constrained algorithms for simple polygons

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)