Memory-constrained algorithms for simple polygons

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

Memory-constrained algorithms for simple polygons

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

13 Citations (Scopus)

80 Downloads (Pure)

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

Access to Document

publishers versionFinal published version, 124 KB

Cite this

@inproceedings{587436b092304adc8cca79599bac119c,

title = "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 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.",

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

year = "2012",

language = "English",

pages = "49--52",

booktitle = "Abstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012)",

publisher = "Universit{\`a} degli Studi di Perugia",

}

Memory-constrained algorithms for simple polygons. / Asano, T.; Buchin, K.; Buchin, M.; Korman, M.; Mulzer, W.; Rote, G.; Schulz, A.

Abstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012). Perugia : Università degli Studi di Perugia, 2012. p. 49-52.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - 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 - 2012

Y1 - 2012

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

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

M3 - Conference contribution

SP - 49

EP - 52

BT - Abstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012)

PB - Università degli Studi di Perugia

CY - Perugia

ER -

Memory-constrained algorithms for simple polygons

Abstract

Access to Document

Fingerprint

Cite this