A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon

DOI10.1142/S0129054118500107zbMath1390.68718MaRDI QIDQ4640339

Pardis Kavand, Ali Mohades

Publication date: 17 May 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

shortest path treecomputational geometrymemory-constrained algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Computing a visibility polygon using few variables
• Space-time trade-offs for stack-based algorithms
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Memory-constrained algorithms for simple polygons
• Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems
• Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
• Computational Geometry in C
• Shortest Path in a Polygon using Sublinear Space.

This page was built for publication: A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon