A new balanced subdivision of a simple polygon for time-space trade-off algorithms

DOI10.1007/s00453-019-00558-9zbMath1421.68177OpenAlexW2964016972MaRDI QIDQ2415364

Eunjin Oh, Hee-Kap Ahn

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8240/

zbMATH Keywords

triangulationshortest pathshortest path treesimple polygontime-space trade-offbalanced subdivision

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Space-time trade-offs for stack-based algorithms
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Upper bounds for time-space trade-offs in sorting and selection
• Triangulating a simple polygon in linear time
• Time-space trade-offs for triangulations and Voronoi diagrams
• Optimal shortest path queries in a simple polygon
• Time-space trade-offs for computing Euclidean minimum spanning trees
• Memory-constrained algorithms for simple polygons
• A time-space trade-off for triangulations of points in the plane
• Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems
• Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
• Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
• Shortest path in a polygon using sublinear space
• Time-space trade-offs for triangulating a simple polygon