Reprint of: Memory-constrained algorithms for simple polygons

DOI10.1016/j.comgeo.2013.11.004zbMathNoneOpenAlexW2067317911MaRDI QIDQ390167

Wolfgang Mulzer, Matias Korman, Maike Buchin, Kevin Buchin, Günter Rote, André Schulz, Tetsuo Asano

Publication date: 22 January 2014

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

triangulationshortest pathsimple polygonconstant workspacespace-time trade-off

Mathematics Subject Classification ID

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

Related Items

Optimal In-place Algorithms for Basic Graph Problems, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, Space-efficient biconnected components and recognition of outerplanar graphs, Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays., Frameworks for designing in-place graph algorithms, A Framework for In-place Graph Algorithms, Space efficient linear time algorithms for BFS, DFS and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-efficient planar convex hull algorithms
• Selection from read-only memory and sorting with minimum data movement
• Multi-pass geometric algorithms
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• Triangulating a simple polygon in linear time
• Triangulating a simple polygon
• Optimal shortest path queries in a simple polygon
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
• Comparison-based time-space lower bounds for selection
• Space-Time Trade-offs for Stack-Based Algorithms
• Computing the Visibility Polygon Using Few Variables
• Undirected connectivity in log-space
• Triangulation and shape-complexity
• Triangulating Simple Polygons and Equivalent Problems
• Slicing an ear using prune-and-search
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Computational Complexity
• Towards in-place geometric algorithms and data structures