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 (19)

• Computing a visibility polygon using few variables
• Time-space trade-offs for triangulations and Voronoi diagrams
• Memory-constrained algorithms for simple polygons
• Frameworks for designing in-place graph algorithms
• Constant-work-space algorithm for a shortest path in a simple polygon
• Rectilinear path problems in restricted memory setup
• Improved Space Efficient Algorithms for BFS, DFS and Applications
• Time-Space Trade-offs for Triangulations and Voronoi Diagrams
• 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
• Title not available (Why is that?)
• Space-efficient biconnected components and recognition of outerplanar graphs
• A Framework for In-place Graph Algorithms
• 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)