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.

Covering a set of line segments with a few squares

Proc. 12th International Conference on Algorithms and Complexity, 2021

To Appear.
@incollection{multihotspots2021,
author = {Gudmundsson, Joachim  and van de Kerkhof, Mees and van Renssen, Andr{\'e}
and Staals, Frank and Wiratma, Lionov and Wong, Sampson},
title = {Covering a set of line segments with a few squares},
booktitle = {Proc. 12th International Conference on Algorithms and Complexity},
year = {2021},
series = {LNCS},
location = {Larnaca, Cyprus},
publisher = {Springer},
category = {trajectories},
note = {To Appear.},
}