Covering a set of line segments with a few squares

Joachim Gudmundsson; Mees van de Kerkhof; André van Renssen; Frank Staals; Lionov Wiratma; Sampson Wong

doi:10.1007/978-3-030-75242-2_20

Covering a set of line segments with a few squares

Joachim Gudmundsson, Mees van de Kerkhof, André van Renssen, Frank Staals, Lionov Wiratma, Sampson Wong^*

^*Corresponding author for this work

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

Abstract

We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. The second is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares.

Original language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	12th International Conference, CIAC 2021, Virtual Event, May 10–12, 2021, Proceedings
Editors	Tiziana Calamoneri, Federico Corò
Publisher	Springer
Pages	286-299
Number of pages	14
Edition	1
ISBN (Electronic)	978-3-030-75242-2
ISBN (Print)	978-3-030-75241-5
DOIs	https://doi.org/10.1007/978-3-030-75242-2_20
Publication status	Published - 5 May 2021

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12701
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Computational geometry
Geometric coverings
Trajectory analysis

Access to Document

10.1007/978-3-030-75242-2_20

978-3-030-75242-2_20Final published version, 481 KBLicence: Taverne

Cite this

Gudmundsson, J., van de Kerkhof, M., van Renssen, A., Staals, F., Wiratma, L., & Wong, S. (2021). Covering a set of line segments with a few squares. In T. Calamoneri, & F. Corò (Eds.), Algorithms and Complexity: 12th International Conference, CIAC 2021, Virtual Event, May 10–12, 2021, Proceedings (1 ed., pp. 286-299). (Lecture Notes in Computer Science; Vol. 12701). Springer. https://doi.org/10.1007/978-3-030-75242-2_20

@inbook{8e0c342084ba49c6b6a26096a16c1e8c,

title = "Covering a set of line segments with a few squares",

abstract = "We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. The second is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares.",

keywords = "Computational geometry, Geometric coverings, Trajectory analysis",

author = "Joachim Gudmundsson and {van de Kerkhof}, Mees and {van Renssen}, Andr{\'e} and Frank Staals and Lionov Wiratma and Sampson Wong",

note = "Invited for a special issue on CIAC 2021 in Theoretical Computer Science (TCS)",

year = "2021",

month = may,

day = "5",

doi = "10.1007/978-3-030-75242-2_20",

language = "English",

isbn = "978-3-030-75241-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "286--299",

editor = "Tiziana Calamoneri and Federico Cor{\`o}",

booktitle = "Algorithms and Complexity",

address = "Germany",

edition = "1",

}

Gudmundsson, J, van de Kerkhof, M, van Renssen, A, Staals, F, Wiratma, L & Wong, S 2021, Covering a set of line segments with a few squares. in T Calamoneri & F Corò (eds), Algorithms and Complexity: 12th International Conference, CIAC 2021, Virtual Event, May 10–12, 2021, Proceedings. 1 edn, Lecture Notes in Computer Science, vol. 12701, Springer, pp. 286-299. https://doi.org/10.1007/978-3-030-75242-2_20

Covering a set of line segments with a few squares. / Gudmundsson, Joachim; van de Kerkhof, Mees; van Renssen, André et al.
Algorithms and Complexity: 12th International Conference, CIAC 2021, Virtual Event, May 10–12, 2021, Proceedings. ed. / Tiziana Calamoneri; Federico Corò. 1. ed. Springer, 2021. p. 286-299 (Lecture Notes in Computer Science; Vol. 12701).

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

TY - CHAP

T1 - Covering a set of line segments with a few squares

AU - Gudmundsson, Joachim

AU - van de Kerkhof, Mees

AU - van Renssen, André

AU - Staals, Frank

AU - Wiratma, Lionov

AU - Wong, Sampson

N1 - Invited for a special issue on CIAC 2021 in Theoretical Computer Science (TCS)

PY - 2021/5/5

Y1 - 2021/5/5

N2 - We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. The second is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares.

AB - We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. The second is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares.

KW - Computational geometry

KW - Geometric coverings

KW - Trajectory analysis

U2 - 10.1007/978-3-030-75242-2_20

DO - 10.1007/978-3-030-75242-2_20

M3 - Chapter

SN - 978-3-030-75241-5

T3 - Lecture Notes in Computer Science

SP - 286

EP - 299

BT - Algorithms and Complexity

A2 - Calamoneri, Tiziana

A2 - Corò, Federico

PB - Springer

ER -

Gudmundsson J, van de Kerkhof M, van Renssen A, Staals F, Wiratma L, Wong S. Covering a set of line segments with a few squares. In Calamoneri T, Corò F, editors, Algorithms and Complexity: 12th International Conference, CIAC 2021, Virtual Event, May 10–12, 2021, Proceedings. 1 ed. Springer. 2021. p. 286-299. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-75242-2_20

Covering a set of line segments with a few squares

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this