Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSharing a pizza: bisecting masses with two cuts
89
0
0.0
(
0
)
Added by
Patrick Schnider
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Assume you have a pizza consisting of four ingredients (e.g., bread, tomatoes, cheese and olives) that you want to share with your friend. You want to do this fairly, meaning that you and your friend should get the same amount of each ingredient. How many times do you need to cut the pizza so that this is possible? We will show that two straight cuts always suffice. More formally, we will show the following extension of the well-known Ham-sandwich theorem: Given four mass distributions in the plane, they can be simultaneously bisected with two lines. That is, there exist two oriented lines with the following property: let $R^+_1$ be the region of the plane that lies to the positive side of both lines and let $R^+_2$ be the region of the plane that lies to the negative side of both lines. Then $R^+=R^+_1cup R^+_2$ contains exactly half of each mass distribution.
rate research
Read More
Assume you have a 2-dimensional pizza with $2n$ ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, that is, your friend and you should each get exactly half of each ingredient. How many cuts do you need? It was recently shown using topological methods that $n$ cuts always suffice. In this work, we study the computational complexity of finding such $n$ cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets $n$ cuts suffice, which does not use any topological methods. We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated.
Let $mathcal{D}$ be a set of $n$ disks in the plane. The disk graph $G_mathcal{D}$ for $mathcal{D}$ is the undirected graph with vertex set $mathcal{D}$ in which two disks are joined by an edge if and only if they intersect. The directed transmission graph $G^{rightarrow}_mathcal{D}$ for $mathcal{D}$ is the directed graph with vertex set $mathcal{D}$ in which there is an edge from a disk $D_1 in mathcal{D}$ to a disk $D_2 in mathcal{D}$ if and only if $D_1$ contains the center of $D_2$. Given $mathcal{D}$ and two non-intersecting disks $s, t in mathcal{D}$, we show that a minimum $s$-$t$ vertex cut in $G_mathcal{D}$ or in $G^{rightarrow}_mathcal{D}$ can be found in $O(n^{3/2}text{polylog} n)$ expected time. To obtain our result, we combine an algorithm for the maximum flow problem in general graphs with dynamic geometric data structures to manipulate the disks. As an application, we consider the barrier resilience problem in a rectangular domain. In this problem, we have a vertical strip $S$ bounded by two vertical lines, $L_ell$ and $L_r$, and a collection $mathcal{D}$ of disks. Let $a$ be a point in $S$ above all disks of $mathcal{D}$, and let $b$ a point in $S$ below all disks of $mathcal{D}$. The task is to find a curve from $a$ to $b$ that lies in $S$ and that intersects as few disks of $mathcal{D}$ as possible. Using our improved algorithm for minimum cuts in disk graphs, we can solve the barrier resilience problem in $O(n^{3/2}text{polylog} n)$ expected time.
The inner structure of the attractor appearing when the Varley-Gradwell-Hassell population model bifurcates from regular to chaotic behaviour is studied. By algebraic and geometric arguments the coexistence of a continuum of neutrally stable limit cycles with different periods in the attractor is explained.
Fixed-order perturbative calculations of fiducial cross sections for two-body decay processes at colliders show disturbing sensitivity to unphysically low momentum scales and, in the case of $Hto gamma gamma$ in gluon fusion, poor convergence. Such problems have their origins in an interplay between the behaviour of standard experimental cuts at small transverse momenta ($p_t$) and logarithmic perturbative contributions. We illustrate how this interplay leads to a factorially divergent structure in the perturbative series that sets in already from the first orders. We propose simple modifications of fiducial cuts to eliminate their key incriminating characteristic, a linear dependence of the acceptance on the Higgs or $Z$-boson $p_t$, replacing it with quadratic dependence. This brings major improvements in the behaviour of the perturbative expansion. More elaborate cuts can achieve an acceptance that is independent of the Higgs $p_t$ at low $p_t$, with a variety of consequent advantages.
We use sampling techniques to find robust constraints on the masses of a possible fourth sequential fermion generation from electroweak oblique variables. We find that in the case of a light (115 GeV) Higgs from a single electroweak symmetry breaking doublet, inverted mass hierarchies are possible for both quarks and leptons, but a mass splitting more than M(W) in the quark sector is unlikely. We also find constraints in the case of a heavy (600 GeV) Higgs in a single doublet model. As recent data from the Large Hadron Collider hints at the existence of a resonance at 124.5 GeV and a single Higgs doublet at that mass is inconsistent with a fourth fermion generation, we examine a type II two Higgs doublet model. In this model, there are ranges of parameter space where the Higgs sector can potentially counteract the effects of the fourth generation. Even so, we find that such scenarios produce qualitatively similar fermion mass distributions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
