Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares (Q1737597): Difference between revisions

Given a set \(\mathcal{L}\) of line segments in \(\mathbb{R}^2\) in a read-only array, the \textit{two-center covering problem} with axis-parallel squares, \textbf{LCOVER}, asks to find two axis-parallel squares of minimum size such that each line segment lies inside at least one of the squares. The \textit{restricted} version of the covering problem requires each line segment to lie completely inside a single square. The slightly different two-center \textit{hitting} problem \textbf{LHIT} requires each line segment to have non-empty intersection with the union of the squares. The authors consider the problems stated above, constructing optimal algorithms for the covering and hitting problems, with constant extra space. They also give a \(\sqrt{2}\)-approximation algorithm for covering and hitting the line segments in \(\mathcal{L}\) with discs instead of squares. Precisely, their results are as follows. Given a set of line segments in \(\mathbb{R}^2\), the authors give: (i) A two-pass algorithm to solve the LCOVER problem optimally, with two axis-parallel squares of minimum size, using only a constant amount of extra space. (ii) A two-pass algorithm to solve the LHIT problem optimally, with two minimum-sized axis-parallel squares optimally, using constant extra space. (iii) A two-pass algorithm to solve the restricted version of the LCOVER problem optimally, by reading the input array sequentially, using constant extra space. Further, the above algorithms also work when the input is a set of polygons instead of line segments. Lastly, the output of the above algorithms gives a \(\sqrt{2}\)-approximation for the problem of covering/hitting line segments by two congruent disks, instead of axis-parallel squares. The proofs are by a careful combinatorial and geometric analysis of the possible configurations, decomposing the input using the \(\ell_\infty\)-Voronoi diagram with the corners of the minimal enclosing rectangle as the sites.