Reprint of : Memory-constrained algorithms for simple polygons

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

13 Citaten (Scopus)


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
Originele taal-2Engels
Pagina's (van-tot)469-479
Aantal pagina's11
TijdschriftComputational Geometry
Nummer van het tijdschrift3, Part B
StatusGepubliceerd - 2014


Duik in de onderzoeksthema's van 'Reprint of : Memory-constrained algorithms for simple polygons'. Samen vormen ze een unieke vingerafdruk.

Citeer dit