Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCircumscribing Polygons and Polygonizations for Disjoint Line Segments
93
0
0.0
(
0
)
Added by
Hugo Akitaya
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 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.
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.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
