Memory-constrained algorithms for simple polygons

DOI10.1016/j.comgeo.2013.04.005zbMath1271.65035arXiv1112.5904OpenAlexW2039511348MaRDI QIDQ2391542

Tetsuo Asano, Maike Buchin, Matias Korman, André Schulz, Kevin Buchin, Wolfgang Mulzer, Günter Rote

Publication date: 31 July 2013

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

algorithmtriangulationshortest pathsimple polygonconstant workspacespace-time trade-off

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (11)

Time-space trade-offs for triangulations and Voronoi diagrams ⋮ Time-Space Trade-offs for Triangulations and Voronoi Diagrams ⋮ A new balanced subdivision of a simple polygon for time-space trade-off algorithms ⋮ Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon ⋮ Space-time trade-offs for stack-based algorithms ⋮ A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon ⋮ Priority Queues and Sorting for Read-Only Data ⋮ A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rectilinear path problems in restricted memory setup

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-efficient planar convex hull algorithms
• Selection from read-only memory and sorting with minimum data movement
• Multi-pass geometric algorithms
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• Triangulating a simple polygon in linear time
• Triangulating a simple polygon
• Optimal shortest path queries in a simple polygon
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
• Space-Time Trade-offs for Stack-Based Algorithms
• Computing the Visibility Polygon Using Few Variables
• Undirected connectivity in log-space
• Triangulation and shape-complexity
• Triangulating Simple Polygons and Equivalent Problems
• Slicing an ear using prune-and-search
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Computational Complexity
• Towards in-place geometric algorithms and data structures

This page was built for publication: Memory-constrained algorithms for simple polygons