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.

Corresponding Publications

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

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

Invited for a special issue on CIAC 2021 in Theoretical Computer Science (TCS)
@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},
  editor = {Calamoneri, Tiziana and Cor{\`o}, Federico},
  location = {Larnaca, Cyprus (online)},
  publisher = {Springer},
  pages = {286--299},
  category = {trajectories},
  doi = {10.1007/978-3-030-75242-2_20},
  url = {https://doi.org/10.1007/978-3-030-75242-2_20},
  note = {Invited for a special issue on CIAC 2021 in Theoretical Computer Science (TCS)},
}

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

Abstr. 36th European Workshop on Computational Geometry (EuroCG), 2020

@article{multihotspots_eurocg,
  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},
  journal = {Abstr. 36th European Workshop on Computational Geometry (EuroCG)},
  year = {2020},
  location = {Wurzburg, Germany (online)},
  numpages = {8},
  category = {trajectories},
  project = {multihotspots2021},
  url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_45.pdf},
}