Reprint of : Memory-constrained algorithms for simple polygons

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

doi:10.1016/j.comgeo.2013.11.004

Reprint of : Memory-constrained algorithms for simple polygons

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

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

13 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. 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	https://doi.org/10.1016/j.comgeo.2013.11.004
Publication status	Published - 2014

Access to Document

10.1016/j.comgeo.2013.11.004

Cite this

@article{5eb9dec17e044997a2b038300202c713,

title = "Reprint of : Memory-constrained algorithms for simple polygons",

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{\"u}nter Rote, Andr{\'e} 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",

author = "T. Asano and K. Buchin and M. Buchin and M. Korman and W. Mulzer and G. Rote and A. Schulz",

year = "2014",

doi = "10.1016/j.comgeo.2013.11.004",

language = "English",

volume = "47",

pages = "469--479",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "3, Part B",

}

TY - JOUR

T1 - Reprint of : 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 - 2014

Y1 - 2014

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. 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

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. 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

U2 - 10.1016/j.comgeo.2013.11.004

DO - 10.1016/j.comgeo.2013.11.004

M3 - Article

SN - 0925-7721

VL - 47

SP - 469

EP - 479

JO - Computational Geometry

JF - Computational Geometry

IS - 3, Part B

ER -

Reprint of : Memory-constrained algorithms for simple polygons

Abstract

Access to Document

Fingerprint

Cite this