Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHelly Numbers of Polyominoes
55
0
0.0
(
0
)
Added by
Matias Korman
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We define the Helly number of a polyomino $P$ as the smallest number $h$ such that the $h$-Helly property holds for the family of symmetric and translated copies of $P$ on the integer grid. We prove the following: (i) the only polyominoes with Helly number 2 are the rectangles, (ii) there does not exist any polyomino with Helly number 3, (iii) there exist polyominoes of Helly number $k$ for any $k eq 1,3$.
rate research
Read More
We study the problem of folding a polyomino $P$ into a polycube $Q$, allowing faces of $Q$ to be covered multiple times. First, we define a variety of folding models according to whether the folds (a) must be along grid lines of $P$ or can divide squares in half (diagonally and/or orthogonally), (b) must be mountain or can be both mountain and valley, (c) can remain flat (forming an angle of $180^circ$), and (d) must lie on just the polycube surface or can have interior faces as well. Second, we give all the inclusion relations among all models that fold on the grid lines of $P$. Third, we characterize all polyominoes that can fold into a unit cube, in some models. Fourth, we give a linear-time dynamic programming algorithm to fold a tree-shaped polyomino into a constant-size polycube, in some models. Finally, we consider the triangular version of the problem, characterizing which polyiamonds fold into a regular tetrahedron.
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special emph{simple} holes guarantee foldability.
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.
Polyominoes are a subset of polygons which can be constructed from integer-length squares fused at their edges. A system of polygons P is interlocked if no subset of the polygons in P can be removed arbitrarily far away from the rest. It is already known that polyominoes with four or fewer squares cannot interlock. It is also known that determining the interlockedness of polyominoes with an arbitrary number of squares is PSPACE hard. Here, we prove that a system of polyominoes with five or fewer squares cannot interlock, and that determining interlockedness of a system of polyominoes including hexominoes (polyominoes with six squares) or larger polyominoes is PSPACE hard.
We introduce a model for random geodesic drawings of the complete bipartite graph $K_{n,n}$ on the unit sphere $mathbb{S}^2$ in $mathbb{R}^3$, where we select the vertices in each bipartite class of $K_{n,n}$ with respect to two non-degenerate probability measures on $mathbb{S}^2$. It has been proved recently that many such measures give drawings whose crossing number approximates the Zarankiewicz number (the conjectured crossing number of $K_{n,n}$). In this paper we consider the intersection graphs associated with such random drawings. We prove that for any probability measures, the resulting random intersection graphs form a convergent graph sequence in the sense of graph limits. The edge density of the limiting graphon turns out to be independent of the two measures as long as they are antipodally symmetric. However, it is shown that the triangle densities behave differently. We examine a specific random model, blow-ups of antipodal drawings $D$ of $K_{4,4}$, and show that the triangle density in the corresponding crossing graphon depends on the angles between the great circles containing the edges in $D$ and can attain any value in the interval $bigl(frac{83}{12288}, frac{128}{12288}bigr)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
