A simple and efficient kinetic spanner

M.A. Abam; M. Berg, de; J. Gudmundsson

doi:10.1145/1377676.1377729

A simple and efficient kinetic spanner

M.A. Abam
, M. Berg, de
, J. Gudmundsson

Algorithms

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

3 Citations (Scopus)

Abstract

We present a new and simple (1+e)-spanner of size O(ne2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/e2).¿s+2(n)), and at each event the spanner can be updated in O(1) time.

Original language	English
Title of host publication	Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)
Place of Publication	New York NY
Publisher	Association for Computing Machinery, Inc.
Pages	306-310
ISBN (Print)	978-1-60558-071-5
DOIs	https://doi.org/10.1145/1377676.1377729
Publication status	Published - 2008

Access to Document

10.1145/1377676.1377729

Cite this

@inproceedings{5d93ab7ee39046a284581cbc6cdb9078,

title = "A simple and efficient kinetic spanner",

abstract = "We present a new and simple (1+e)-spanner of size O(ne2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/e2).¿s+2(n)), and at each event the spanner can be updated in O(1) time.",

author = "M.A. Abam and \{Berg, de\}, M. and J. Gudmundsson",

year = "2008",

doi = "10.1145/1377676.1377729",

language = "English",

isbn = "978-1-60558-071-5",

pages = "306--310",

booktitle = "Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)",

publisher = "Association for Computing Machinery, Inc.",

address = "United States",

}

A simple and efficient kinetic spanner. / Abam, M.A.; Berg, de, M.; Gudmundsson, J.
Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008). New York NY: Association for Computing Machinery, Inc., 2008. p. 306-310.

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

TY - GEN

T1 - A simple and efficient kinetic spanner

AU - Abam, M.A.

AU - Berg, de, M.

AU - Gudmundsson, J.

PY - 2008

Y1 - 2008

N2 - We present a new and simple (1+e)-spanner of size O(ne2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/e2).¿s+2(n)), and at each event the spanner can be updated in O(1) time.

AB - We present a new and simple (1+e)-spanner of size O(ne2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/e2).¿s+2(n)), and at each event the spanner can be updated in O(1) time.

U2 - 10.1145/1377676.1377729

DO - 10.1145/1377676.1377729

M3 - Conference contribution

SN - 978-1-60558-071-5

SP - 306

EP - 310

BT - Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)

PB - Association for Computing Machinery, Inc.

CY - New York NY

ER -

A simple and efficient kinetic spanner

Abstract

Access to Document

Fingerprint

Cite this