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 comes from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to k = 4 unit-sized, axis-parallel squares. We give linear time algorithms for k ≤ 3 and an O(n logn) time algorithm for k = 4. 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. For k = 2 and k = 3 we construct data structures of size O(nα(n)logn) in O(nα(n)logn) time, so that we can test if an arbitrary subtrajectory can be k-covered in O(logn) time. 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. We give O(n2α(n) log2 n) time algorithms for k ≤ 2.