Memory-Constrained Algorithms for Simple Polygons

Abstract

A constant-workspace algorithm has read-only access to an input array and may use only O(1) additional words of $O(\log n)$ 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.

Preprint appeared in EuroCG 2012

References in corpus (1)

• Memory-Constrained Algorithms for Simple Polygons

Cited by in corpus (4)

• Memory-Constrained Algorithms for Simple Polygons
• A Time-Space Trade-off for Computing the k-Visibility Region of a Point in a Polygon
• Time-Space Trade-offs for Triangulations and Voronoi Diagrams
• Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees