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)
Download Local Copy View Slides Export Citation 
@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

Theoretical Computer Science, 2022

Special issue on CIAC 2021
Download Local Copy View Slides Export Citation 
@article{multihotspots2022,
  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 = {Theoretical Computer Science},
  year = {2022},
  publisher = {Elsevier},
  pages = {25},
  doi = {10.1016/j.tcs.2022.04.053},
  url = {https://doi.org/10.1016/j.tcs.2022.04.053},
  category = {trajectories},
  note = {Special issue on CIAC 2021},
  project = {multihotspots2021},
}

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

Download Local Copy View Slides Export Citation 
@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},
}