Covering a set of line segments with a few squares

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.