اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFolding Polyominoes with Holes into a Cube
100
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 squ
ares 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.
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$.
It is shown that there exists a dihedral acute triangulation of the three-dimensional cube. The method of constructing the acute triangulation is described, and symmetries of the triangulation are discussed.
We introduce a computational origami problem which we call the segment folding problem: given a set of $n$ line-segments in the plane the aim is to make creases along all segments in the minimum number of folding steps. Note that a folding might alte
r the relative position between the segments, and a segment could split into two. We show that it is NP-hard to determine whether $n$ line segments can be folded in $n$ simple folding operations.
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $delta=frac{8}{5pi}approx 0.509$. This implies that any set of (not necessarily equal)
squares of total area $A leq frac{8}{5}$ can always be packed into a disk with radius 1; in contrast, for any $varepsilon>0$ there are sets of squares of total area $frac{8}{5}+varepsilon$ that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square $left(frac{1}{2}right)$, circles in a square $left(frac{pi}{(3+2sqrt{2})}approx 0.539right)$ and circles in a circle $left(frac{1}{2}right)$ have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
