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

DOI10.4230/LIPICS.ISAAC.2017.61zbMATH Open1457.68295arXiv1709.09932MaRDI QIDQ5136282FDOQ5136282

Eunjin Oh, Hee-Kap Ahn

Publication date: 25 November 2020

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

Recommendations

• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• Time-space trade-offs for triangulating a simple polygon
• Time-space trade-offs for triangulating a simple polygon
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Memory-constrained algorithms for simple polygons

zbMATH Keywords

shortest pathsimple polygontime-space trade-offshortest path tree

Mathematics Subject Classification ID

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

Cites Work

• Computational geometry. Algorithms and applications.
• Triangulating a simple polygon in linear time
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems
• Upper bounds for time-space trade-offs in sorting and selection
• Memory-constrained algorithms for simple polygons
• Space-time trade-offs for stack-based algorithms
• Shortest path in a polygon using sublinear space
• A time-space trade-off for triangulations of points in the plane
• Time-space trade-offs for triangulating a simple polygon

Cited In (2)

• AN IMPROVED ALGORITHM FOR SUBDIVISION TRAVERSAL WITHOUT EXTRA STORAGE
• Title not available (Why is that?)

This page was built for publication: A new balanced subdivision of a simple polygon for time-space trade-off algorithms

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