Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDisjoint axis-parallel segments without a circumscribing polygon
82
0
0.0
(
0
)
Added by
Minghui Jiang
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We construct a family of 17 disjoint axis-parallel line segments in the plane that do not admit a circumscribing polygon.
rate research
Read More
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.
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.
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.
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.
Suppose an escaping player moves continuously at maximum speed 1 in the interior of a region, while a pursuing player moves continuously at maximum speed $r$ outside the region. For what $r$ can the first player escape the region, that is, reach the boundary a positive distance away from the pursuing player, assuming optimal play by both players? We formalize a model for this infinitesimally alternating 2-player game that we prove has a unique winner in any region with locally rectifiable boundary, avoiding pathological behaviors (where both players can have winning strategies) previously identified for pursuit-evasion games such as the Lion and Man problem in certain metric spaces. For some regions, including both equilateral triangle and square, we give exact results for the critical speed ratio, above which the pursuing player can win and below which the escaping player can win (and at which the pursuing player can win). For simple polygons, we give a simple formula and polynomial-time algorithm that is guaranteed to give a 10.89898-approximation to the critical speed ratio, and we give a pseudopolynomial-time approximation scheme for arbitrarily approximating the critical speed ratio. On the negative side, we prove NP-hardness of the problem for polyhedral domains in 3D, and prove stronger results (PSPACE-hardness and NP-hardness even to approximate) for generalizations to multiple escaping and pursuing players.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
