TY - JOUR

T1 - Memory-constrained algorithms for simple polygons

AU - Asano, T.

AU - Buchin, K.

AU - Buchin, M.

AU - Korman, M.

AU - Mulzer, W.

AU - Rote, G.

AU - Schulz, A.

PY - 2013

Y1 - 2013

N2 - A constant-work-space algorithm has read-only access to an input array and may use only O(1) additional words of bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O(n2) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n2/s) time.

AB - A constant-work-space algorithm has read-only access to an input array and may use only O(1) additional words of bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O(n2) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n2/s) time.

U2 - 10.1016/j.comgeo.2013.04.005

DO - 10.1016/j.comgeo.2013.04.005

M3 - Article

VL - 46

SP - 959

EP - 969

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 8

ER -