Constant-work-space algorithms for geometric problems

zbMATH Open1404.68182MaRDI QIDQ2968076FDOQ2968076

Authors: Wolfgang Mulzer, Günter Rote, Yajun Wang, Tetsuo Asano 

Publication date: 9 March 2017

Recommendations

• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Constant-work-space algorithm for a shortest path in a simple polygon
• Memory-constrained algorithms for simple polygons
• Time-space trade-offs for triangulations and Voronoi diagrams
• Time-space trade-offs for triangulations and Voronoi diagrams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Cited In (20)

• Computing a visibility polygon using few variables
• Time-space trade-offs for triangulations and Voronoi diagrams
• Time-space trade-offs for triangulations and Voronoi diagrams
• Improved space efficient algorithms for BFS, DFS and applications
• Memory-constrained algorithms for simple polygons
• Frameworks for designing in-place graph algorithms
• Experimental study of compressed stack algorithms in limited memory environments
• Constant-work-space algorithm for a shortest path in a simple polygon
• Rectilinear path problems in restricted memory setup
• A framework for in-place graph algorithms
• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Prune-and-search with limited workspace
• Space efficient linear time algorithms for BFS, DFS and applications
• Space-time trade-offs for stack-based algorithms
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Optimal In-place Algorithms for Basic Graph Problems
• Constant work-space algorithms for facility location problems
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• Space-efficient biconnected components and recognition of outerplanar graphs
• Reprint of: Memory-constrained algorithms for simple polygons

This page was built for publication: Constant-work-space algorithms for geometric problems

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