Shortest path in a polygon using sublinear space

DOI10.20382/JOCG.V7I2A3MaRDI QIDQ2970464zbMATH OpenOpenAlexFDO

Authors Sariel Har-Peled

Publication date 30 March 2017

Full work available at URL https://arxiv.org/abs/1412.0779

Mathematics Subject Classification ID

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

Abstract: $$ We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon $Polygon$ with $n$ vertices in a read only memory, and additional working memory of size $Space$, the new algorithm computes the shortest path (in $Polygon$) in $O(n^2/,Space)$ expected time. This requires several new tools, which we believe to be of independent interest.

Recommendations

• Shortest Path in a Polygon using Sublinear Space.
• Memory-constrained algorithms for simple polygons
• Constant-work-space algorithm for a shortest path in a simple polygon
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms

Cited in

(16)

• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Time and space efficient algorithms for shortest paths between convex polygons
• Optimal shortest path queries in a simple polygon
• Time-space trade-offs for triangulations and Voronoi diagrams
• Approximate Shortest Paths in Polygons with Violations
• Shortest paths in simple polygons with polygon-meet constraints
• Constant-work-space algorithm for a shortest path in a simple polygon
• Optimal algorithms for geometric centers and depth
• Cospanning characterizations of violator and co-violator spaces
• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Constant work-space algorithms for facility location problems
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• Shortest Path in a Polygon using Sublinear Space.
• Maximal distortion of geodesic diameters in polygonal domains
• Finding a shortest Hamiltonian path inside a simple polygon
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms

This page was built for publication: Shortest path in a polygon using sublinear space

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