Corrigendum to: Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares, Theoretical Computer Science 769 (2019) 63--74


Abstract in English

In the paper Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares, TCS Volume 769 (2019), pages 63--74, the LHIT problem is proposed as follows: For a given set of non-intersecting line segments ${cal L} = {ell_1, ell_2, ldots, ell_n}$ in $I!!R^2$, compute two axis-parallel congruent squares ${cal S}_1$ and ${cal S}_2$ of minimum size whose union hits all the line segments in $cal L$, and a linear time algorithm was proposed. Later it was observed that the algorithm has a bug. In this corrigendum, we corrected the algorithm. The time complexity of the corrected algorithm is $O(n^2)$.

Download