Abstract
A constant-work-space 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 input size. We show how to triangulate a plane straight-line graph with n vertices in O(n2) time and constant workspace. We also consider the problem of preprocessing a simple n-gon P for shortest path queries, where P is given by the ordered sequence of its 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.
| Original language | English |
|---|---|
| Title of host publication | Abstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012) |
| Place of Publication | Perugia |
| Publisher | Università degli Studi di Perugia |
| Pages | 49-52 |
| Publication status | Published - 2012 |
Fingerprint Dive into the research topics 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. (2012). Memory-constrained algorithms for simple polygons. In Abstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012) (pp. 49-52). Università degli Studi di Perugia.