Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLine and Plane Cover Numbers Revisited
327
0
0.0
(
0
)
Added by
Alexander Wolff
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A measure for the visual complexity of a straight-line crossing-free drawing of a graph is the minimum number of lines needed to cover all vertices. For a given graph $G$, the minimum such number (over all drawings in dimension $d in {2,3}$) is called the emph{$d$-dimensional weak line cover number} and denoted by $pi^1_d(G)$. In 3D, the minimum number of emph{planes} needed to cover all vertices of~$G$ is denoted by $pi^2_3(G)$. When edges are also required to be covered, the corresponding numbers $rho^1_d(G)$ and $rho^2_3(G)$ are called the emph{(strong) line cover number} and the emph{(strong) plane cover number}. Computing any of these cover numbers -- except $pi^1_2(G)$ -- is known to be NP-hard. The complexity of computing $pi^1_2(G)$ was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~$G$, whether $pi^1_2(G)=2$. We further show that the universal stacked triangulation of depth~$d$, $G_d$, has $pi^1_2(G_d)=d+1$. Concerning~3D, we show that any $n$-vertex graph~$G$ with $rho^2_3(G)=2$ has at most $5n-19$ edges, which is tight.
rate research
Read More
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph $G$ that is embedded in Euclidean space. The edges of $G$ need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in $Theta(log chi (G))$, while for 3D the minimum scan time is not upper bounded by $chi (G)$. We use this relationship to prove that the existence of a constant-factor approximation implies $P=NP$, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of $frac{3}{2}$, even for bipartite graphs; conversely, we present a $frac{9}{2}$-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $kleq chi(G)^c$. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in $O(nlog n)$ time and $O(nlog n)$ space, where $n$ is the total number of vertices of all obstacles. The algorithm is time-optimal because $Omega(nlog n)$ is a lower bound. It has been an open problem for over two decades whether the space can be reduced to $O(n)$. In this paper, we settle it by solving the problem in $O(nlog n)$ time and $O(n)$ space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point $s$ in $O(nlog n)$ time and $O(n)$ space, such that given any query point $t$, the length of a shortest path from $s$ to $t$ can be computed in $O(log n)$ time and a shortest path can be produced in additional time linear in the number of edges of the path.
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in $mathbb{R}^d$. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on $varepsilon>0$ and $din mathbb{N}$ of the minimum lightness of $(1+varepsilon)$-spanners, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}logDelta)$ in the plane, where $Deltageq Omega(sqrt{n})$ is the emph{spread} of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness $tilde{O}(varepsilon^{-(d+1)/2})$ in dimensions $dgeq 3$. Recently, Bhore and T{o}th (2020) established a lower bound of $Omega(varepsilon^{-d/2})$ for the lightness of Steiner $(1+varepsilon)$-spanners in $mathbb{R}^d$, for $dge 2$. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions $dgeq 2$. In this work, we show that for every finite set of points in the plane and every $varepsilon>0$, there exists a Euclidean Steiner $(1+varepsilon)$-spanner of lightness $O(varepsilon^{-1})$; this matches the lower bound for $d=2$. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $operatorname{rb-index}(k)$ be the maximum of $operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $operatorname{rb-index}(k) eq k$, and we prove that for $kge 5$, [ frac{40lfloor (k-1)/2 rfloor -8}{19} %Birgit: leqoperatorname{rb-index}(k)leq 10 bigglfloorfrac{k}{7}biggrfloor + 11. ] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 lfloorfrac{k}{7}rfloor + 11$ vertices can be computed in $O(nlog n)$ time.
K{a}rolyi, Pach, and T{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $lceil (n+5)/6rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
