FREE ELECTRONIC LIBRARY - Thesis, dissertations, books

Pages:   || 2 |

«Abstract In eighteenth century England John Montagu, the fourth Earl of Sandwich, forever changed the course of humanity when he developed a way to ...»

-- [ Page 1 ] --

Ham Sandwich Cuts

Math 480b SAGE

Andy Barr, Maddie Romansic, Lauren Bobel, Chloe Huber, Matthew Junge

March 12th, 2010


In eighteenth century England John Montagu, the fourth Earl of Sandwich, forever

changed the course of humanity when he developed a way to simultaneously satiate

his ravenous appetite, play cards with his chums and keep his hands clean. No one

knows how the epiphany dawned upon the Earl, however most historians agree it

was probably divine guidance. Inspiration aside, the moment Montagu requested his valet bring him meat tucked between two pieces of bread, the scope and direction of mathematics would be irreversibly altered.

Ever the egalitarian, Montagu became obsessed with being able to share his sandwiches without bias between him and his friends. From this flurry of creativity

and scientific curiosity arose the following question:

Given a sandwich consisting of bread, cheese and ham constructed in any manner, does there exist a cut that will divide all three ingredients equally between slices?

It was not until Borsuk-Ulam came along and proved a theorem whose corollary answered the Earl’s question with a resounding, ”Yes!”. The statement of the Ham

Sandwich Theorem is as follows:

Theorem 0.1 (Ham Sandwich).

If A1,..., An+1 are bounded measurable sets in Rn+1, there exists an n-plane in Rn+1 that bisects each of them simultaneously.

We see that the R3 case of the theorem completely answers the Earl’s question.

However, it does not yield any insight into how one finds such a cut. Our group set out to answer a special case of the theorem. Namely, we will address the following theorem.

Theorem 0.2 (R2 Polygon Case).

Given two polygons in R2 there exists a line that simultaneously bisects the area of both.

To answer this question we have developed a sage interact that takes as input vertices of two polygons and an error bound. With these it plots the polygons and uses a binary search to generate a line that cuts the area of the two polygons to fit within the error bound.

Contents 1 Proving the Theorem 4 2 Coding out the Code 5

2.1 Three Teams are Better than One................... 5 3 The Teams/Tasks 6

3.1 P-Team.................................. 6 3.1.1 Building Polygons........................ 6 3.1.2 Let There be Line........................ 7

3.2 The L-Team Experience

–  –  –

1 Proving the Theorem Though not the most glamorous part of our project, we feel it important to give a little exposition pertaining to pure mathematics of the theorem. First we state the

Borsuk-Ulam Theorem:

Theorem 1.1 (Borsuk-Ulam).

Let S 2 ⊂ R3 denote the unit sphere. Given a continuous map f : S 2 → R2, there is a point of x ∈ S 2 such that f (x) = f (−x).

The proof of the theorem relies on algebraic topology pertaining to antipode preserving maps and homotopy theory. We will omit these details and assume that Borsuk-Ulam holds. With this, we offer a proof of the two dimensional polygon case

of the Ham Sandwich Theorem:

Theorem 1.2.

Given two polygons in R2 there exists a line that simultaneously bisects the area of both.

Proof. We take two bounded polygonal regions A1 and A2 in the plane R2 × 1 contained in R3, we wish to show there exists a line L in this plane that bisects the area of both polygons.

Given a point u ∈ S 2, let us consider the plane P in R3 that passes through the origin that has u as its unit normal vector. This plane divides R3 into two half-spaces; let fi (u) equal the area of that portion of Ai that lies on the same side of P as does the vector u.

If u is the unit vector k = 0, 0, 1, then fi (u) = area(Ai ) and if u = −k then fi (u) = 0. This is true since our polygons lie in the plane R2 × 1 determined by k.

Thus, if u = k and u = −k we have the plane P intersects the plane R2 × 1 in a line L that splits R2 × 1 into two half planes, and fi (u) is the area of that part of Ai that lies on one side of this line.

Replacing u by −u gives us the same plane P, but the other half space, so that fi (−u) is the area of that part of Ai that lies on the other side of P from u. This

gives us the following:

–  –  –

The Borsuk-Theorem gives us a point u ∈ S 2 for which F (u) = F (−u). This implies that fi (u) = fi (−u) for i = 1, 2, Hence fi (u) = 2 Ai and we have bisected both polygons as desired.

2 Coding out the Code Unfortunately the previous theorem is only a result that proves existence of such a line L. Though the result is very pretty and somewhat surprising, the Earl of Sandwich would probably be left unsatisfied. For although we now know such a cut exists, we are still left scratching our heads with no information about how to make such a cut. The great Earl no doubt spent hours upon hours, days upon days, years upon years holed up in his kitchen working his chefs to the bone and tediously implementing the most basic of utensil algorithms to find his cut. Fortunately for us, the advent of the computer allows our team to make more cuts than our friend Montagu could ever dream of making.

Our project very naturally separated into three subgoals:

1. Draw and find the areas of two polygons and be able to find the areas of the sub-polygons generated by an intersecting line.

2. Implement a line-finding algorithm to approximately bisect our polygons.

3. Create a nice interact in Sage that showcases our work and makes the Earl proud.

2.1 Three Teams are Better than One To attack these areas of our code we decided to split our group of five into two task

force ‘teams’:

P-Team who would deal with the polygons and the points obtained from intersecting lines with said polygons. This team consists of Maddie, Lauren and Matt.

L-Team would deal with the lines, in particular the area-bisecting line. This team is Andy and Chloe.

Our construction of these two tasks mostly proved to be disjoint pieces of code in which L-Team could pass their arguments into P-Team’s area and polygon generating functions. However, there was some work in the gluing together of code which transitions into the final team in our group.

A-Team (Short for All-Team and included all five members.) A-Teams job was to make everything work and implement the interact.

3 The Teams/Tasks The natural partitioning of our project led to an equally natural partitioning of our paper. We will divide the exposition on our code into three sections, each corresponding to one of the teams in our group.

3.1 P-Team P-Team essentially had two tasks. First, we needed a nice way to interact with polygons, i.e. plotting their vertices, finding their area and computing their centroids.

Second, we had to make our polygons interact well with lines so we could easily implement the cutting.

Let us first turn out attention to the construction of our polygons and the computing of their essential information.

–  –  –

Additionally, we had some interest in locating the centroid since that seemed

like a good starting point for generating a bisecting line. The centroid formula is:

–  –  –

With the above formulas coded and a nice way to draw polygons we were able to generate an interact that took as input vertices that plots two polygons and the line through their centroids. While providing the areas of each.

This still left us with the task of generating four new polygons from an intersecting line.

3.1.2 Let There be Line It proved somewhat difficult to figure out how to find the lower and upper polygons that result from intersecting a polygon with our dividing line. The method that we finally decided on was to write the line in the form ax + by = c and represent each edge of our polygon as a line segment. Thus, we need only calculate whether the line intersects each edge and place all of the points below the intersection into a list creating the lower polygon. To do this we utilized matrix.rightsolve in sage and implemented a careful tracking loop to keep our new vertices in order.

The end result of P-Team’s labors is the following interact:

–  –  –

Notice that we have input boxes for the vertices. And, upon entering two polygons, we deliver the area and centroid of each as well as the dividing line that intersects both centroids. With the line in place we calculate the lower polygons of our two major polygons and display them in a different color. Lastly, we print the area and run a simple output of “too big” or “too small” which decides if the polygon has been bisected or not.

3.2 The L-Team Experience Like the river winds through the forest floor only to emerge, flowing with an inner grace and powerful beauty, in the bosom of the ocean, our coding objectives wound through the floors of our hearts, twisting and turning, everchanging, only to break out of the constraints of our souls and into the sage notebook as a functioning line generating algorithm.

The point of the preceding poorly punctuated run-on sentence poetry is to illustrate that our process for finding a bisecting line was not mechanical and anything but direct. Below we give an outline of our thought process in making the hamline.

3.2.1 Gearing Up It was L Team’s job to deal with code that would eventually generate a line approximately bisecting the area of any two polygons. Our thought was that we would begin with the line passing through the centroids of the two polygons, and then by comparing the relative areas of the four new polygons created by the intersection of the two original polygons and that line, make a series of informed translations and rotations of the intersecting line: the “hamline”.

This prompted the creation of a hamline class, a class of line which could be initialized as a line passing through the two centroids of our polygons, and represented by a 3-tuple (a, b, c) representative of the equation of a line ax + by = c. We originally had a y = mx + b hamline which freaked out when our lines were vertical.

Handling vertical and horizontal lines would always be hassle.

Hamline would also know other useful information about itself, including its normal and later how to translate and rotate.

3.2.2 Translate and Rotate The original plan was to compare the areas of the four polygons in our plane, and

make the decision to:

1. translate or rotate

2. in which direction, i.e. positive vs. negative, clockwise or counterclockwise

3. to what magnitude To what magnitude to translate hamline along it’s normal, and to what degree to rotate hamline about its “pivot point” - the so-called point equidistant from the two centroids - would be a calculation based on the ratio of the four areas. However, half way through the formation of this calculation, Andy had an epiphany...

3.2.3 The Binary Search Instead of comparing the areas of four polygons to make an informed translation or rotation, we would use a binary search inspired algorithm until our translate or rotate was within a certain margin of error or within a certain number of steps. At this stage, we were mainly concerned with our rotate method. Rotate would turn hamline into a vector, and place it normal to the original line. Then, it would make the decision to either rotate by progressively half of the angle it had rotated before in either a clockwise or counterclockwise direction.

Translate would go through a similar process: beginning with the line parallel to hamline and passing through either the largest or smallest value y-coordinate vertex, then translating along the normal.

However, we soon became bogged down in how to finish execution and how to alternate effectively between translate and rotate. If we did not set a fixed number of steps (number of rotations or number of translations) and let binary search continue until our hamline was effectively dividing the polygons within a certain margin or error our search might never end (since during the course of one translation or rotation it might be impossible to get close enough to the ideal line). But if a number of steps is set arbitrarily, it is possible that translate or rotate might leave us with a less accurate hamline. We also started to question our choice of pivot point, and whether it should be fixed or dynamic.

3.2.4 Epiphany After all the thought put into the translate and rotate methods, ultimately we decided the best way to find a line bisecting two polygons was to effectively draw a rectangle of best fit around the polygons and draw lines from one point on the perimeter of the rectangle to another point on the perimeter.

This approximation is not very nice, however, if the dimensions of the rectangle are very different from each other, since the number of points taken from the 2 pairs of sides is the same.

3.2.5 To Class Conversion We had so many methods manipulating lines and polygons that it made more sense that the lines and polygons knew how to store and give information about themselves. Making a hamline class and polygon class of our own also solved serious scope and hierarchical issues within the code. It also kept our information organized and retrievable. It made flow control possible to keep track of in a reasonable manner.

Before, our code was a mess, but now we have 3 classes and a main method that takes less than 30 lines. Yay!

3.2.6 Fine Tuning: Error Bound Implementation The error bound was created because in order to achieve machine precision we would have had to created a bunch of lines. In order to put an upper bound on our calculations, we decided to allow the user to input an error bound. We used this error to determine the size of our steps between our two points. See, we partitioned the line segment between the maxima and minima of our x and y and created lines with those steps based on approaching the area with a tolerance given by the error bound.

Pages:   || 2 |

Similar works:

«The Geologic History of the Long Valley Caldera and the Landforms Created Within Abstract The Long Valley caldera eruption was a major explosion which resulted in the destruction of a wide area, along with hundreds of feet of ash, called the Bishop Tuff, being dumped on the immediate area. Though the eruption was catastrophic, activity still continues within the Long Valley area today. The magma chamber that continues to lie beneath the Long Valley caldera heats the water for the Hot Creek...»

«Methodist History, 49:2 (January 2011) METhODIST INTERRACIAL COOpERATION IN ThE pROgRESSIvE ERA: AMANDA BERRy SMITh AND EMMA RAy1 Priscilla PoPe-levison More than two decades ago, in a volume dedicated to American Methodism’s bicentennial celebration, Lewis V. Baldwin proffered a list of desiderata to engage Methodist scholarship for the next centennial. The following item on Baldwin’s list has gone largely unheeded: “More time and energy could be devoted to studies of blacks who were...»

«Cost Calculations for Supplemental Examination and Reexamination Fee Methodology. The Office uses an Activity Based Information (ABI) methodology to determine its historical costs on a per-process, per-service, or per-material basis, including the particular processes and services addressed in this rulemaking. The ABI methodology follows the full cost guidance outlined in OMB circular A-25 and the fee setting guidance outlined in the Government Accountability Office (GAO) report on Federal User...»

«    Media Data and Social Science Research:   Problems and Approaches                    February 2014                  Cline Center for Democracy  University of Illinois at Urbana‐Champaign                      Cline Center for Democracy, University of Illinois ABSTRACT   News media provide a unique source of information on important societal developments, both contemporary and historical. Consequently, over the past forty years, social...»

«FTLRS POSITIONING FOR THE EU/NASA ALTIMETER CALIBRATION PROJECT GAVDOS E. C. Pavlis (1) and S. P. Mertikas (2) (1) Joint Center for Earth Systems Technology, UMBC & NASA Goddard, epavlis@JCET.umbc.edu/Fax: +1-410-455-5868, (2) Tech. Univ. of Crete, Chania, Greece Abstract The Eastern Mediterranean area is one of great interest for its intense tectonic activity as well as for its regional oceanography. Recent observations convincingly demonstrated the importance of the area for regional...»

«European Journal for Research on the Education and Learning of Adults, Vol.3, No.2, 2012, pp. 135-153 Discursive turns from ‘Bildung’ to managerialism Memory-work of the Finnish adult education generations Karin Filander University of Tampere, Finland (karin.filander@uta.fi) Abstract The article focuses on the struggles over ethos in academic adult education tradition that grows from the frameworks of student generations in Finnish adult education. It brings together elements of present-day...»

«Introduction: Sound as Popular Culture Jens Gerrit Papenburg and Holger Schulze Researching sound as popular culture is the study of sound as both an integral and constitutive part of culture. The investigation of sound as popular culture would be more aptly described as a study through sound than a study about sound. An examination of sound as popular culture explores epistemologies reaching beyond the dualisms of subject–object and text–context. Those three research goals guide the...»

«TALES of an ART DEALER The History of Vose Galleries Boston Robert C.Vose Jr. Preface H Y S I C A L A P P E A R A N C E and manner first come to mind when I think of Bob Vose. A tall fair-complexioned man, bald when I knew him, with piercing eyes, slightly stooped as he aged, who carried himself with a subtle dignity. His manner was that of an Edwardian gentleman whose gentility went beyond the social graces. He spoke quietly and listened as if he was truly interested in what other people were...»

«FREEDOM OF THE PRESS, EXPRESSION, AND INFORMATION IN SPAIN CHALLENGES AND OBSTACLES FACED BY THE SPANISH NEWS MEDIA IN GATHERING AND DISSEMINATING INFORMATION Javier Sierra 4 October 2014 [corrected text, January 2015] Supported by the Open Society Foundations, Millbank Tower, 21–24 Millbank, London SW1P 4QP United Kingdom Contents Introduction.. 3 Freedom of the Press and Freedom of Expression. 1. 5 1.1 Overview of Press Freedom in Spain in Historic Perspective. 5 1.1.1 The Press during...»

«28.2 (December 2006): 45–58 ISSN 0210-6124 Roger Waters’ Poetry of the Absent Father: British Identity in Pink Floyd’s The Wall Jorge Sacido Romero Luis Miguel Varela Cabo Universidad de Santiago de Compostela iasacido@usc.es fmluis@usc.es In spite of being one the most remarkable and arresting products of late-twentiethcentury British popular culture, Pink Floyd’s The Wall has received little scholarly attention. This paper focuses on how in The Wall and in its companion album, The...»

«A DIALECTAL READING OF THE HISTORY OF TRANSLATION1 Jairo Sánchez Galvis Jairo.Sanchez@sta.uwi.edu University of the West Indies Abstract The translation of dialect is one of the most difficult and yet interesting challenges facing literary translators. Although theoretical contributions about dialect translation develop mainly from 1960, this article proposes a historical reading of the history of translation from antiquity to the first half of the 20th century, inquiring about the...»

«COURSE AUDITS Definitions, Explanations and Examples Overview The Course Audits comprise two major reports with additional summaries: • The Course Offering Audit for each subject lists the distribution of undergraduate courses by class-size categories. It also lists each class, which falls below the minimum class size designation in the current year. To help with the administration of the minimum class-size policy, a historical listing of all such courses along with their enrollments are...»

<<  HOME   |    CONTACTS
2016 www.dis.xlibx.info - Thesis, dissertations, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.