Memory-constrained algorithms for simple polygons

DOI10.1016/J.COMGEO.2013.04.005MaRDI QIDQ2391542zbMATH OpenOpenAlexFDO

Authors Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, André Schulz, 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, http://www.sciencedirect.com/science/article/pii/S0925772113000382

zbMATH Keywords

algorithmconstant workspaceshortest pathsimple polygonspace-time trade-offtriangulation

Mathematics Subject Classification ID

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

Abstract: A constant-workspace algorithm has read-only access to an input array and may use only O(1) additional words of $O(logn)$ bits, where $n$ is the size of the input. We assume that a simple $n$-gon is given by the ordered sequence of its vertices. We show that we can find a triangulation of a plane straight-line graph in $O(n^2)$ time. We also consider preprocessing a simple polygon for shortest path queries when the space constraint is relaxed to allow $s$ words of working space. After a preprocessing of $O(n^2)$ time, we are able to solve shortest path queries between any two points inside the polygon in $O(n^2/s)$ time.

Recommendations

• Computing area-optimal simple polygonizations
• Time-space trade-offs for triangulating a simple polygon
• Time-space trade-offs for triangulating a simple polygon
• scientific article; zbMATH DE number 3945383
• A contribution to triangulation algorithms for simple polygons
• A fast algorithm for polygon operations
• A convex hull algorithm for planar simple polygons
• EFFICIENT APPROXIMATION OF CONVEX POLYGONS
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time

Cites work

• Comparison-based time-space lower bounds for selection
• Computational Complexity
• Computational geometry. Algorithms and applications.
• Computing the visibility polygon using few variables
• Constant-work-space algorithms for geometric problems
• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Data streams: algorithms and applications.
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Multi-pass geometric algorithms
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Optimal shortest path queries in a simple polygon
• Selection and sorting with limited storage
• Selection from read-only memory and sorting with minimum data movement
• Slicing an ear using prune-and-search
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Space-efficient planar convex hull algorithms
• Space-time trade-offs for stack-based algorithms
• Towards in-place geometric algorithms and data structures
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time
• Triangulating Simple Polygons and Equivalent Problems
• Triangulation and shape-complexity
• Undirected connectivity in log-space
• Upper bounds for time-space trade-offs in sorting and selection

Cited in

(23)

• An efficient algorithm for finding the CSG representation of a simple polygon
• Time-space trade-offs for triangulations and Voronoi diagrams
• A time-space trade-off for computing the k-visibility region of a point in a polygon
• Rectilinear path problems in restricted memory setup
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Space-time trade-offs for stack-based algorithms
• Constant-work-space algorithms for geometric problems
• Shortest path in a polygon using sublinear space
• Time-space trade-off for finding the k-visibility region of a point in a polygon
• Constant-work-space algorithm for a shortest path in a simple polygon
• Time-space trade-offs for triangulations and Voronoi diagrams
• Reprint of: Memory-constrained algorithms for simple polygons
• scientific article; zbMATH DE number 2080878 (Why is no real title available?)
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Priority queues and sorting for read-only data
• Space-time trade-offs for stack-based algorithms
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• Experimental study of compressed stack algorithms in limited memory environments
• Memory efficient algorithms for cactus graphs and block graphs
• Constant workspace algorithms for computing relative hulls in the plane
• Shortest paths of mutually visible robots
• Simplified linear-time Jordan sorting and polygon clipping

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

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