Memory-constrained algorithms for simple polygons

T. Asano, K. Buchin, M. Buchin, M. Korman, W. Mulzer, G. Rote, A. Schulz

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)959-969
JournalComputational Geometry
Volume46
Issue number8
DOIs
Publication statusPublished - 2013

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. (2013). Memory-constrained algorithms for simple polygons. Computational Geometry, 46(8), 959-969. https://doi.org/10.1016/j.comgeo.2013.04.005