Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
106
0
0.0
(
0
)
Added by
Sanjib Sadhu Mr
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper discusses the problem of covering and hitting a set of line segments $cal L$ in ${mathbb R}^2$ by a pair of axis-parallel squares such that the side length of the larger of the two squares is minimized. We also discuss the restricted version of covering, where each line segment in $cal L$ is to be covered completely by at least one square. The proposed algorithm for the covering problem reports the optimum result by executing only two passes of reading the input data sequentially. The algorithm proposed for the hitting and restricted covering problems produces optimum result in $O(n)$ time. All the proposed algorithms are in-place, and they use only $O(1)$ extra space. The solution of these problems also give a $sqrt{2}$ approximation for covering and hitting those line segments $cal L$ by two congruent disks of minimum radius with same computational complexity.
rate research
Read More
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)$.
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.
We construct a family of 17 disjoint axis-parallel line segments in the plane that do not admit a circumscribing polygon.
Deciding whether a family of disjoint axis-parallel line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.
We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of $m$ sets over $n$ elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight query complexities. On one hand, first we show an adaptation of the streaming algorithm presented in Har-Peled et al. [2016] to the sub-linear query model, that returns an $alpha$-approximate cover using $tilde{O}(m(n/k)^{1/(alpha-1)} + nk)$ queries to the input, where $k$ denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of $k$, the required number of queries is $tilde{Omega}(m(n/k)^{1/(2alpha)})$, even for estimating the optimal cover size. Moreover, we prove that even checking whether a given collection of sets covers all the elements would require $Omega(nk)$ queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter $k$. On the other hand, we show that this bound is not optimal for larger values of the parameter $k$, as there exists a $(1+varepsilon)$-approximation algorithm with $tilde{O}(mn/kvarepsilon^2)$ queries. We show that this bound is essentially tight for sufficiently small constant $varepsilon$, by establishing a lower bound of $tilde{Omega}(mn/k)$ query complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
