اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn universal covers for carpenters rule folding
322
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present improved universal covers for carpenters rule folding in the plane.
قيم البحث
اقرأ أيضاً
We introduce the study of forcing sets in mathematical origami. The origami material folds flat along straight line segments called creases, each of which is assigned a folding direction of mountain or valley. A subset $F$ of creases is forcing if th
e global folding mountain/valley assignment can be deduced from its restriction to $F$. In this paper we focus on one particular class of foldable patterns called Miura-ori, which divide the plane into congruent parallelograms using horizontal lines and zig-zag vertical lines. We develop efficient algorithms for constructing a minimum forcing set of a Miura-ori map, and for deciding whether a given set of creases is forcing or not. We also provide tight bounds on the size of a forcing set, establishing that the standard mountain-valley assignment for the Miura-ori is the one that requires the most creases in its forcing sets. Additionally, given a partial mountain/valley assignment to a subset of creases of a Miura-ori map, we determine whether the assignment domain can be extended to a locally flat-foldable pattern on all the creases. At the heart of our results is a novel correspondence between flat-foldable Miura-ori maps and $3$-colorings of grid graphs.
Tusnadys problem asks to bound the discrepancy of points and axis-parallel boxes in $mathbb{R}^d$. Algorithmic bounds on Tusnadys problem use a canonical decomposition of Matouv{s}ek for the system of points and axis-parallel boxes, together with oth
er techniques like partial coloring and / or random-walk based methods. We use the notion of emph{shallow cell complexity} and the emph{shallow packing lemma}, together with the chaining technique, to obtain an improved decomposition of the set system. Coupled with an algorithmic technique of Bansal and Garg for discrepancy minimization, which we also slightly extend, this yields improved algorithmic bounds on Tusnadys problem. For $dgeq 5$, our bound matches the lower bound of $Omega(log^{d-1}n)$ given by Matouv{s}ek, Nikolov and Talwar [IMRN, 2020] -- settling Tusnadys problem, upto constant factors. For $d=2,3,4$, we obtain improved algorithmic bounds of $O(log^{7/4}n)$, $O(log^{5/2}n)$ and $O(log^{13/4}n)$ respectively, which match or improve upon the non-constructive bounds of Nikolov for $dgeq 3$. Further, we also give improved bounds for the discrepancy of set systems of points and polytopes in $mathbb{R}^d$ generated via translations of a fixed set of hyperplanes. As an application, we also get a bound for the geometric discrepancy of anchored boxes in $mathbb{R}^d$ with respect to an arbitrary measure, matching the upper bound for the Lebesgue measure, which improves on a result of Aistleitner, Bilyk, and Nikolov [MC and QMC methods, emph{Springer, Proc. Math. Stat.}, 2018] for $dgeq 4$.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of
edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $operatorname{rb-index}(S)$ denote the smallest size of a perfect rain
bow polygon for a colored point set $S$, and let $operatorname{rb-index}(k)$ be the maximum of $operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $operatorname{rb-index}(k) eq k$, and we prove that for $kge 5$, [ frac{40lfloor (k-1)/2 rfloor -8}{19} %Birgit: leqoperatorname{rb-index}(k)leq 10 bigglfloorfrac{k}{7}biggrfloor + 11. ] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 lfloorfrac{k}{7}rfloor + 11$ vertices can be computed in $O(nlog n)$ time.
Let $P$ be a set of $2n$ points in convex position, such that $n$ points are colored red and $n$ points are colored blue. A non-crossing alternating path on $P$ of length $ell$ is a sequence $p_1, dots, p_ell$ of $ell$ points from $P$ so that (i) all
points are pairwise distinct; (ii) any two consecutive points $p_i$, $p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i eq j$. We show that there is an absolute constant $varepsilon > 0$, independent of $n$ and of the coloring, such that $P$ always admits a non-crossing alternating path of length at least $(1 + varepsilon)n$. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + varepsilon)n$ points of $P$. This is a properly colored matching whose segments are pairwise disjoint and intersected by common line. For bo
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
