Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn universal covers for carpenters rule folding
322
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 present improved universal covers for carpenters rule folding in the plane.
rate research
Read More
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 the 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 other 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 rainbow 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
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
