No Arabic abstract
We prove that for all positive integers $n$ and $k$, there exists an integer $N = N(n,k)$ satisfying the following. If $U$ is a set of $k$ direction vectors in the plane and $mathcal{J}_U$ is the set of all line segments in direction $u$ for some $uin U$, then for every $N$ families $mathcal{F}_1, ldots, mathcal{F}_N$, each consisting of $n$ mutually disjoint segments in $mathcal{J}_U$, there is a set ${A_1, ldots, A_n}$ of $n$ disjoint segments in $bigcup_{1leq ileq N}mathcal{F}_i$ and distinct integers $p_1, ldots, p_nin {1, ldots, N}$ satisfying that $A_jin mathcal{F}_{p_j}$ for all $jin {1, ldots, n}$. We generalize this property for underlying lines on fixed $k$ directions to $k$ families of simple curves with certain conditions.
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.
Convex geometry is a closure space $(G,phi)$ with the anti-exchange property. A classical result of Edelman and Jamison (1985) claims that every finite convex geometry is a join of several linear sub-geometries, and the smallest number of such sub-geometries necessary for representation is called the convex dimension. In our work we find necessary and sufficient conditions on a closure operator $phi$ of convex geometry $(G,phi)$ so that its convex dimension equals 2, equivalently, they are represented by segments on a line. These conditions can be checked in polynomial time in two parameters: the size of the base set $|G|$ and the size of the implicational basis of $(G,phi)$.
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.
Given integers $k$ and $m$, we construct a $G$-arc-transitive graph of valency $k$ and an $L$-arc-transitive oriented digraph of out-valency $k$ such that $G$ and $L$ both admit blocks of imprimitivity of size $m$.