Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCovering a set of line segments with a few squares
183
0
0.0
(
0
)
Added by
Sampson Wong
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the fewest sensors (the hitting points). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable.
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)$.
Given a planar straight-line graph $G=(V,E)$ in $mathbb{R}^2$, a emph{circumscribing polygon} of $G$ is a simple polygon $P$ whose vertex set is $V$, and every edge in $E$ is either an edge or an internal diagonal of $P$. A circumscribing polygon is a emph{polygonization} for $G$ if every edge in $E$ is an edge of $P$. We prove that every arrangement of $n$ disjoint line segments in the plane has a subset of size $Omega(sqrt{n})$ that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to $mathbb{R}^3$. We show that it is NP-complete to decide whether a given graph $G$ admits a circumscribing polygon, even if $G$ is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.
Suppose we have an arrangement $mathcal{A}$ of $n$ geometric objects $x_1, dots, x_n subseteq mathbb{R}^2$ in the plane, with a distinguished point $p_i$ in each object $x_i$. The generalized transmission graph of $mathcal{A}$ has vertex set ${x_1, dots, x_n}$ and a directed edge $x_ix_j$ if and only if $p_j in x_i$. Generalized transmission graphs provide a generalized model of the connectivity in networks of directional antennas. The complexity class $exists mathbb{R}$ contains all problems that can be reduced in polynomial time to an existential sentence of the form $exists x_1, dots, x_n: phi(x_1,dots, x_n)$, where $x_1,dots, x_n$ range over $mathbb{R}$ and $phi$ is a propositional formula with signature $(+, -, cdot, 0, 1)$. The class $exists mathbb{R}$ aims to capture the complexity of the existential theory of the reals. It lies between $mathbf{NP}$ and $mathbf{PSPACE}$. Many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, are complete for $exists mathbb{R}$. Continuing this line of research, we show that the recognition problem of generalized transmission graphs of line segments and of circular sectors is hard for $exists mathbb{R}$. As far as we know, this constitutes the first such result for a class of directed graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
