Reprint of: Memory-constrained algorithms for simple polygons

DOI10.1016/J.COMGEO.2013.11.004MaRDI QIDQ390167zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Memory-constrained algorithms for simple polygons
• Constant-work-space algorithm for a shortest path in a simple polygon
• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Constant-work-space algorithms for geometric problems
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon

Cites work

• Comparison-based time-space lower bounds for selection
• Computational Complexity
• Computational geometry. Algorithms and applications.
• Computing the visibility polygon using few variables
• Constant-work-space algorithms for geometric problems
• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Data streams: algorithms and applications.
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Multi-pass geometric algorithms
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Optimal shortest path queries in a simple polygon
• Selection and sorting with limited storage
• Selection from read-only memory and sorting with minimum data movement
• Slicing an ear using prune-and-search
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Space-efficient planar convex hull algorithms
• Space-time trade-offs for stack-based algorithms
• Towards in-place geometric algorithms and data structures
• Triangulating Simple Polygons and Equivalent Problems
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time
• Triangulation and shape-complexity
• Undirected connectivity in log-space
• Upper bounds for time-space trade-offs in sorting and selection

Cited in

(9)

• Extra space during initialization of succinct data structures and dynamical initializable arrays
• A framework for in-place graph algorithms
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
• Space efficient linear time algorithms for BFS, DFS and applications
• scientific article; zbMATH DE number 2080878 (Why is no real title available?)
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Space-efficient biconnected components and recognition of outerplanar graphs
• Optimal In-place Algorithms for Basic Graph Problems
• Frameworks for designing in-place graph algorithms

This page was built for publication: Reprint of: Memory-constrained algorithms for simple polygons

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