Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecognizing Generalized Transmission Graphs of Line Segments and Circular Sectors
72
0
0.0
(
0
)
Added by
Wolfgang Mulzer
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Let $S subset mathbb{R}^2$ be a set of $n$ sites, where each $s in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t in S$ if and only if $|st| leq r_s + r_t$, i.e., if the disks with centers $s$ and $t$ and respective radii $r_s$ and $r_t$ intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph $T(S)$ is the directed graph with vertex set $S$ and a directed edge from a site $s$ to a site $t$ if and only if $|st| leq r_s$, i.e., if $t$ lies in the disk with center $s$ and radius $r_s$. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in $D(S)$ and in $T(S)$. These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in $D(S)$ and in $T(S)$ can be found in $O(n log n)$ expected time, and that the (weighted) girth of $D(S)$ can be found in $O(n log n)$ expected time. For this, we develop new tools for batched range searching that may be of independent interest.
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.
Let $P subset mathbb{R}^2$ be a planar $n$-point set such that each point $p in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q in P$, there is an edge from $p$ to $q$ if and only if $d(p, q) leq r_p$. Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H subseteq G$ with vertex set $P$ so that for any two vertices $p,q in P$, we have $d_H(p, q) leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (log n + log Psi))$ time, where $Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n log^5 n)$ time, independent of $Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can reach a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(log nlog Psi)$ to the query time and $O(n log Psi)$ to the space.
We present sweeping line graphs, a generalization of $Theta$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting that could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
