### Abstract

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.
Keywords: Space–time trade-off; Constant workspace; Triangulation; Shortest path; Simple polygon
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, André Schulz
Memory-constrained algorithms for simple polygons
Computational Geometry, Volume 46, Issue 8, October 2013, Pages 959-969
http://dx.doi.org/10.1016/j.comgeo.2013.04.005

Original language | English |
---|---|

Pages (from-to) | 469-479 |

Number of pages | 11 |

Journal | Computational Geometry |

Volume | 47 |

Issue number | 3, Part B |

DOIs | |

Publication status | Published - 2014 |

## Fingerprint Dive into the research topics of 'Reprint of : Memory-constrained algorithms for simple polygons'. Together they form a unique fingerprint.

## Cite this

Asano, T., Buchin, K., Buchin, M., Korman, M., Mulzer, W., Rote, G., & Schulz, A. (2014). Reprint of : Memory-constrained algorithms for simple polygons.

*Computational Geometry*,*47*(3, Part B), 469-479. https://doi.org/10.1016/j.comgeo.2013.11.004