Streaming algorithms for line simplification under the Fréchet distance

M.A. Abam; M. Berg, de; P. Hachenberger; A. Zarei

Streaming algorithms for line simplification under the Fréchet distance

M.A. Abam
, M. Berg, de
, P. Hachenberger
, A. Zarei

Algorithms

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

238 Downloads (Pure)

Abstract

We study the following variant of the well-known linesimplification problem: we are getting a possibly infinite sequence of points p0, p1, p2, . . . defining a polygonal path, and as we receive the points we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage so that we cannot store all the points. We analyze the competitive ratio of our algorithm, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points, and compare the error of our simplification to the error of the optimal simplification with k points.

Original language	English
Title of host publication	Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria
Editors	O. Aichholzer, T. Hackl
Place of Publication	Graz, Austria
Publisher	Verlag der Technischen Universität Graz
Pages	77-80
ISBN (Print)	978-3-902465-62-7
Publication status	Published - 2007
Event	conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21 - Duration: 19 Mar 2007 → 21 Mar 2007

Conference

Conference	conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21
Period	19/03/07 → 21/03/07
Other	EWCG 2007, Graz, Austria

Access to Document

Metis210773Final published version, 265 KB

Cite this

@inproceedings{f330aae6c5b54a8485eeac56af3112be,

title = "Streaming algorithms for line simplification under the Fr{\'e}chet distance",

abstract = "We study the following variant of the well-known linesimplification problem: we are getting a possibly infinite sequence of points p0, p1, p2, . . . defining a polygonal path, and as we receive the points we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage so that we cannot store all the points. We analyze the competitive ratio of our algorithm, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points, and compare the error of our simplification to the error of the optimal simplification with k points.",

author = "M.A. Abam and \{Berg, de\}, M. and P. Hachenberger and A. Zarei",

year = "2007",

language = "English",

isbn = "978-3-902465-62-7",

pages = "77--80",

editor = "O. Aichholzer and T. Hackl",

booktitle = "Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria",

publisher = "Verlag der Technischen Universit{\"a}t Graz",

note = "conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21 ; Conference date: 19-03-2007 Through 21-03-2007",

}

Abam, MA, Berg, de, M, Hachenberger, P & Zarei, A 2007, Streaming algorithms for line simplification under the Fréchet distance. in O Aichholzer & T Hackl (eds), Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria. Verlag der Technischen Universität Graz, Graz, Austria, pp. 77-80, conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21, 19/03/07.

Streaming algorithms for line simplification under the Fréchet distance. / Abam, M.A.; Berg, de, M.; Hachenberger, P. et al.
Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria. ed. / O. Aichholzer; T. Hackl. Graz, Austria: Verlag der Technischen Universität Graz, 2007. p. 77-80.

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

TY - GEN

T1 - Streaming algorithms for line simplification under the Fréchet distance

AU - Abam, M.A.

AU - Berg, de, M.

AU - Hachenberger, P.

AU - Zarei, A.

PY - 2007

Y1 - 2007

N2 - We study the following variant of the well-known linesimplification problem: we are getting a possibly infinite sequence of points p0, p1, p2, . . . defining a polygonal path, and as we receive the points we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage so that we cannot store all the points. We analyze the competitive ratio of our algorithm, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points, and compare the error of our simplification to the error of the optimal simplification with k points.

AB - We study the following variant of the well-known linesimplification problem: we are getting a possibly infinite sequence of points p0, p1, p2, . . . defining a polygonal path, and as we receive the points we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage so that we cannot store all the points. We analyze the competitive ratio of our algorithm, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points, and compare the error of our simplification to the error of the optimal simplification with k points.

M3 - Conference contribution

SN - 978-3-902465-62-7

SP - 77

EP - 80

BT - Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria

A2 - Aichholzer, O.

A2 - Hackl, T.

PB - Verlag der Technischen Universität Graz

CY - Graz, Austria

T2 - conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21

Y2 - 19 March 2007 through 21 March 2007

ER -

Streaming algorithms for line simplification under the Fréchet distance

Abstract

Conference

Access to Document

Fingerprint

Cite this