MTH301 Math Research
Welcome to the MTH301 Math Research Page
How to edit Wiki pages: See the Wikipedia editing cheat sheet.
Participants:
- Yonit Boursany
- Leah Karker
- Leona Sparaco
- Joe O'Rourke
Link to Moodle pages for MTH301. However, I think we will use this wiki instead of Moodle. In line with that thought, I will duplicate the two links from Moodle below.
Contents
- 1 Resources
- 2 Hypotheses and Theorems and Lemmas
- 3 Theorem.
- 4 Three Figures
- 5 Poster Draft
- 6 1-flush vs. 2-flush: Statistics
- 7 Paper Drafts
- 8 Proofs
Resources
- My initial beamer presentation is here.
- Here is the raw .tex file: beamer.tex.
- The Dumitrescu-Jiang paper is here.
Hypotheses and Theorems and Lemmas
28 Jan 2010
For Arbitrary Shapes
Hypotheses:
- The best sweep can always be achieved by two sweeps: three or more are never needed to achieve the minimum sweep cost.
- The best sweep can be found by surrounding the shape with the minimum perimeter parallelogram, and then slant-sweeping twice, with cost half the perimeter.
Hairpins
Define a hairpin as two segments of unit length joined at an endpoint of each.
- The best sweep of a hairpin depends on the angle theta between them.
- For θ ≥ 73 deg = 2 arccos[4/5], it is best to sweep each pin separately, for a cost of 2.
- for θ < this angle, it is best to sweep down the bisector, and then sweep the resulting line segment, for a cost of cos(θ/2) + 2sin(θ/2).
We believe that this description is consistent with the parallelogram Hypothesis above.
4 Feb 2010
Proved
- Lemma 1: 1 sweep (either orthogonal or slanted) will suffice if and only if all points are collinear.
Proof: First we assume that one sweep will suffice. If it is not the case that all points in a shape lie on the same line, then there exist three non-collinear points. A sweep encountering these points will move all three along parallel lines. To reach one point, these three lines must coincide. This of course is a contradiction since we have assumed that the three points do not lie on the same line. Thus, if one sweep will suffice then all points must be collinear. Now, we assume instead that all points are collinear. So there exists some line on which all points in the shape are located. Clearly, sweeping along this line will move all points to the single point located at the end of the sweep. Therefore, one sweep suffices if and only if all points are collinear
- Corollary 1: If 1 sweep suffices then the cost of the (optimal) sweep will equal the length of the line segment connecting the two points furthest from each other.
- Lemma 2: If limited to 2 sweeps, the minimal cost will be half the perimeter of the minimal parallelogram.
Proof. (Sketch?). We know the first sweep must sweep the entire shape into a line, by Lemma 1 above. Let the cost of the first sweep be d1, and the cost of the second d2. We know from Corollary 1 that d2 is the length of the line into which the first sweep compresses the shape. And the total cost of both sweeps is d1+d2. We want to minimize d1+d2. The two sweeps determine a parallelogram, whose side lengths constitute d1+d2.
Investigated
- How might cost be decreased if we are allowed three (or more) sweeps?
- Can Dumitrescu/Jiang's proof of Theorem 2 (constrained variants, discrete points along perimeter of triangle) be applied to a continuous distribution?
Minimum Perimeter Parallelogram
I (JOR) got interested in computing the minimum perimeter enclosing parallelogram (MPEP). It will likely be useful to have an implementation to test out hypotheses, if for no other reason. I wrote a brute-force search program in Mathematica. Essentially it tries all possible pairs of directions, specified by two angles α and β. Eventually I will link to the code from here, but for now I just want to record the fact that an implementation exists, albeit in a crude form. Here is a typical output, showing the best parallelogram enclosing six random points.
- Question: Is it true that the MPEP for a triangle always has one side flush with a triangle side?
11 Feb 2010
Two Sweeps Not Always Best
- Found examples where 3 and 5 sweeps are better than 2. (Rectangle with a line--or thin rectangle--coming out diagonally from one corner)
- New question: Is 3 (or less) sweeps always best?
MPEP for Triangle: One Side Always Flush?
- Asked: Can we always rotate an enclosing parallelogram so that the triangle has one side flush with a triangle side? No. The diagonal of a parallelogram is longer than the length. If we have a triangle along the diagonal that is very thin (triangle height approaching the length of the diagonal) we are unable to rotate the parallelogram so that one side is flush with a triangle side.
- Right triangle: Examples suggest that the MPEP is always flush against the two shorter sides of the triangle.
Mathematica Code for MPEP
The Mathematica code comes in three notebooks:
- LineLine.nb: Intersecting two lines
- Extremes.nb: Finding the extreme points of a set in a given direction.
- EnclosingParallelogram.nb: Search for MPEP.
Instructions for how to use them is in the latter file, in a comment at the top. If you right-click on these links and save the files on a machine that has Mathematica, then you will be able to launch and run them.
Literature Search for Minimum Perimeter Enclosing Shapes
- Student project at McGill Univ. claims this: "The minimum perimeter rectangle enclosing a convex polygon P has a side collinear with an edge of the polygon."
- This claim is verified in the Wikipedia article.
- There is a paper entitled "Minimum-Perimeter Enclosing k-gon". This is recent, 2006. They prove a key flush edge lemma, which may be what we are looking for. I know the lead author of whom we can ask questions. Here is their paper: Mitchell.MinPerim.pdf
18 Feb 2010
Experiment for θ=120
Here is the experiment I (JOR) promised in today's meeting. I started with an isosceles triangle/hairpin. I chose the angle θ=120 deg, which, because greater than 73 deg, implies that the best parallelogram includes the two edges meeting at the θ angle. Then I gradually increased the horizontal leg of the triangle, making it increasingly non-isosceles. You can see that the brute-force searching program concludes that, independent of the mismatch in the length of the two edges of the hairpin, the MPEP still is flush with the two edges meeting at the θ angle. (Obviously the figures below are not to the same scale!)
Experiment for θ=30
The situation is different if we start with an angle smaller than our critical 73 deg. Here I started with 30 deg. For all x > 1.2, there are two edges flush. Not sure what to make of this...
Proof that 2 sweeps don't suffice for all figures
Consider a 1x1 square with a diagonal of length √2 jutting out from one corner. By the 1-flush lemma, there are two ways of enclosing this shape in a parallelogram, namely (a) within a 2x2 square or (b) within a parallelogram formed by connecting the vertex of the diagonal with the two adjacent vertices of the square (this makes two sides of the figure, then reflect those sides to complete.) (a) has cost 4, and (b) cost 2√5=4.47 which are each greater than the cost of sweeping the diagonal and then the square (2+√2=3.41), requiring at least 3 sweeps.
25 Feb 2010
Flush Function Mathematica Notebook
Here is the Mathematica calculations we did today.
- FlushFunction.nb: Flush Function Notebook
Today's favorite image!
Here is the result of using ContourPlot[ FlushFunction[] ]:
I solved the equation for b in terms of a. Here it is in raw form. Did not try to simplify or reorganize.
Beamer Skeleton Files
Here is a .zip file containing everything needed to run off the beamer skeleton we created today:
- MarchPresentation.zip: Beamer skeleton
You need to download this file, and unzip it, usually by double-clicking on it (depends if Windows/MacOS/Linux). Once unzipped, you can edit MarchPresentation.tex in any text editor, save, and then LaTeX. On my Mac I use TeXShop. On Linux I use pdflatex. Exactly how to do this varies with the context.
Here is the .pdf file it produces when LaTeX'ed. This file is in the .zip file, but if you want to see it on its own, here it is:
- MarchPresentation.pdf: PDF created by the above beamer skeleton
4Mar10
The links above to MarchPresentation.zip (and to MarchPresentation.pdf) have been updated to reflect our work today. I just replaced the files they point to.
13 Mar 2010: Observations
I have two observations.
- First, this minor variant of our square-with-diagonal-antenna seems also to require three sweeps, in fact the same three sweeps. I've just filled out the antenna into the pink parallelogram.
- This example (which is nonconvex) makes me realize that there is a hypothesis close to our very first falsified hypothesis that we haven't yet killed:
- Hypothesis: The optimal sweeping of any convex polygon uses only two sweeps.
23 Mar 2010
This image needs an explanation!
- Light colors: 1 side flush
- Dark colors: 2 sides flush
Now determined that the above image is misleading in several ways.
26 Mar 2010
The new computation, correcting the 1-flush cost from (h+1), used above, to (h+x), where x is the length of the base plus whatever extra (if any) is need to reach the foot of the altitude. For the 1-flush rectangle has dimensions h by x, not h by 1. I also corrected an unrelated renormalizing error, just a mental bug on my part.
- Color scheme same as above:
- Light colors: 1 side flush
- Dark colors: 2 sides flush
- Circle is centered on (0,0), radius 1.
This is quite a surprise to me! It seems to be saying that many of the cases that we thought were 2-flush are actually 1-flush. Let me give one example that I worked out by hand as a check.
- (1,a,b)=(1,3/4,3/4). Isosceles triangle, with an angle > 83 at apex, larger than our critical hairpin angle of 73 deg. So we thought this was a 2-flush case, well under our cube-root curve, well within the dark green. I compute the 2-flush cost is a+b=3/2=1.50. But I get a competing value of 1.49 for 1-flush against either the a or b edge. (And this case doesn't even involve the new base computation, because the altitude projects inside the triangle.) That cube-root curve we had is the correct transition between 1- and 2-flush, just green vs. light green, but when the others (all six options) are all included (correctly!), 2-flush loses.
So, there are two questions:
- Does this new image make sense??
- The digital boundary between the 2-flush and the 1-flush regions is almost perfectly fit by a circle. Why???
6 Apr 2010
Theorem.
Normalize triangle so that the longest edge=1. Let θ be the ab-apex. If θ ≥ 90, the min cost sweep is determined by the parallelogram 2-flush against a and b. If θ ≤ 90, the min cost sweep is determined by the rectangle 1-flush against the shortest side (which must be a or b by the normalization).
Proof.
- 2-flush for obtuse angles. Let b<a. Construct side l=b+x so that x,h,a form a right triangle. Want to show h+l>a+b. Since h+x>a by triangle inequality, we are done.
- 1-flush for acute angles. Compare h+a to a+b, b+1, a+1. We have a,b<1 and h<b, so h+a<a+b<a+1<b+1, where a is the shortest side.
- I seem to have two proofs of this same thing written down, and I think they both need to be changed to proofs by contradiction, because as they are, they just end in a true conclusion. I'll put them both up though, maybe someone can let me know why they're different and can change them to better proofs:
- 1-flush against 1 is worse than 1-flush against the shortest side (a). A=.5bh'<.5ab, since h'<a by the triangle inequality. So h<ab. We have a+b ≤ h+1<ab+1. So a+b<ab+1 and a(1-b)<1-b. Since a<1, we are done.
- 1-flush against 1 is worse than 1-flush against the shortest side (a). A=h=h'a. h+1>h'+b, so h'(1-b)<1-b, which is true since h'<1.
What are we missing? (Also, my apologies for not adding the diagrams. I can draw them in Illustrator, but I'm not sure how to upload them here.)
I think we were trying to do the two different angle cases (obtuse and acute between shorter sides), but I am confused too looking at my notes.
The 2nd of your last proofs (1-flush against short side beats 1-flush against 1) seems right to me. h+1>h'+b is what we are trying to show, not something we know already. We start our proof with the fact that we know h'<1 (we have constructed a right triangle with hypotenuse 1 and one of the short sides h'). From there we have h'(1-b)<1-b. Distributing and rearranging: h'+b<1+h'b. From the equation for area we know h=h'b. So substitution gives us: h'+b<1+h, which is what we wanted. I have this labeled as the "acute" case.
I am confused on what I have as the "obtuse" case in my notes. Using the same method I described above, we seemed to have proved a+b<1+ab. Remind me why we were trying to prove this? What does this show?
So we have proofs: Obtuse, 2-flush against shorter sides is better than 1-flush against shortest side. Acute, 1-flush against shortest side is better than 2-flush against two shorter sides is better than 2-flush against longest and shortest side is better than 2-flush against longest and mid-length side. And then (also in the acute case), 1-flush against shortest side is better than 1-flush against longest side.
So it seems that in the acute case we need only show that 1-flush against the shortest side is better than 1-flush against the mid-length side (which seems pretty clear, right?)
In the obtuse case we still need to show that 2-flush against shorter sides is better than 1-flush against the longest side. I think we did this during our last meeting but I don't understand what I have written. [Just to be thorough, I guess we also should include in our proof that 2-flush against shorter sides is better than 2-flush against the longest and shortest and 2-flush against longest and mid-length (though both of these statements are obvious). But we could make a general note of this at the beginning of our proofs since it does not depend on the acute/obtuse angle.]
Three Figures
I drew these figures for possible use in the poster... --JOR
Poster Draft
Here is a rough draft of the poster, as a crude image. I put in all the figures we agreed upon, extending the first sweeping figure to show that two sweeps and four sweeps both result in the same cost. The only text with which I was careful was the title, and the proof. I've put all the various pieces in boxes which are 'grouped' in Illustrator, which means they move as a unit. (You can ungroup them by selecting and choosing ungroup someplace [I have all the shortcuts memorized and I no longer remember how to find the options in the menus].) I had to use a .jpg image for our Mathematica plot, because the original was so huge I couldn't save the file. So we may see some rasterization in the final print.
I left the background white, mainly because I couldn't think of a color that would work with everything else. I'm not the greatest judge of colors. :-/ You can make suggestions. Or if you know how to change colors, go ahead (direct selection tool, color dialog box, fill color, etc.).
But your main task is to add appropriate text, size it appropriately, and arrange all the pieces as you want. The text is all Times New Roman, except θ etc. which use font Symbol. I used italics for the variables. You can add text with the Font tool (T), and then adjust the size and font. You don't have to stick to the pt-size options they give you. There is a general scale tool that I used to make the title. If you can't accomplish something that you want to do, you can describe it to and leave it for me.
- [First draft image removed]
Because I am not absolutely certain which format is best, or which will work in your environment, I am providing three versions. Start with the first, and work your way down:
- [Use 2nd-draft links below instead]
- SweepingPoster.ai: Illustrator CS3 .ai format
- SweepingPoster.eps: Illustrator CS3 .eps format
- SweepingPoster.pdf: Illustrator CS3 .pdf format
Please save the poster in CS3 format, because that's all I have on my workstation. There are options in the Save dialog box to save it in "legacy" versions. If you can't figure out how to do it, go ahead and save in CS4, and I'll downconvert myself.
Second Draft
Here is the revised poster, followed by links to the PDF and the AI format.
Links
- SweepingPoster.pdf: Second draft, .pdf format
- SweepingPoster.ai: Illustrator CS3 .ai format
First Draft PowerPoint
Poster contents copied to PowerPoint slides.
- 21 Apr link removed.
Second Draft PowerPoint
Link:
- SweepingPosterSlides.pptx: Draft (22 Apr). Result of our Thursday meeting. (Original draft removed.)
1-flush vs. 2-flush: Statistics
I ran one trial, generating random polygons up to 10 sides. In 891 instances, 55% of the min perim paras were 1-flush, and 45% 2-flush. However, there were 7% numerically close calls among the 1-flush, which might have been 2-flush. And given that my random polygon generator has a bias toward one long edge, I would say the data is consistent with the hypothesis that the 1-flush/2-flush percentages are 50%-50% on truly random polygons, with exact computation.
A later experiment, for k=10 (decagons), 400 trials, 1-flush=195, 2-flush=205, 49% vs. 51%. So it seems for larger k, the breakdown might approach 50%-50%.
Link added 30Apr: Here are the 50 random quadrilaterals. I couldn't figure out how to copy them out easily, so I left them in a Mathematica Notebook. So you'll have to launch Mathematica to view them.
- Quads50.nb: 50 Random Quads
Paper Drafts
Canadian Conference on Computational Geometry:
I updated the paper in four ways [4May10]:
- I flipped the figures so that a is shortest. I also labeled the little foot x. I can adjust if you want different notation.
- I added the hard-case figure (but no explanation).
- I added a corollary (Corollary 9) that clarifies something I was thinking about. It is not important, and will likely have to be deleted to reach four pages anyway.
- I added the explicit equation of the cubic curve for the hard case.
Updates [6May10]:
- Incorporated Leona's triangles.tex (thanks!).
- Explained the (a,b)-graph
- Explained the hard case.
- Cited Corollary 9 as justifying the cases in the proof.
Links:
- SweepTwice.pdf: Draft (updated 6 May).
- SweepTwice.tex: Draft (updated 6 May).
Proofs
For Both Cases
Let a,b,1 be the sides of our triangle such that a<b<1.
Observe that a+b<a+1<b+1.
So 2-flush against the two shorter sides always beats the other 2-flush cases.
Acute Case
We will denote the height of the parallelogram that is flush against side a (which we had previously called h_a) by a'.
- 1-flush against shortest side beats 2-flush cases
Because we have a right triangle, a'<b. Thus, a+a'<a+b. So 1-flush against a beats 2-flush against a,b and hence beats all 2-flush cases.
- 1-flush against shortest side beats 1-flush against longest side
Let h be the height of the parallelogram flush against the longest side. Because we have a right triangle, a'<1. So, a'(1-a)<1-a a'-a'a<a-a a'+a<1+a'a. From our area equations ½(1)(h)=½(a')(a), so h=a'a. Thus, a'+a<1+h.
- 1-flush against shortest side beats 1-flush against median-length side
Define b' as the height of the parallelogram flush against side b. We know that a<b, so a(1-(a'/b))<b(1-(a'/b)) a-(aa'/b)<b-(ba'/b) a-(aa'/b)<b-a' a+a'<b+(aa'/b). From our area equations ½aa'=½bb', so aa'=bb' and hence aa'/b=b'. Thus, a+a'<b+b'.
So 1-flush against the shortest side wins in all cases.
Obtuse Case
Define a',b',and h as before.
- 2-flush against shortest sides beats 1-flush against shortest side.
Extend side a by length x so that a perpendicular line of length a' with intersect the b,1 vertex (so we have created a right triangle with sides x,a',b). The cost of sweeping 1-flush against a will be a+x+a'. By the triangle inequality, b<a'+x. Thus, a+b<a+x+a'.
- 2-flush against shortest sides beats 1-flush against median-length side.
Extend side b by length y so that a perpendicular line of length b' with intersect the a,1 vertex (so we have created a right triangle with sides y,b',a). The cost of sweeping 1-flush against b will be b+y+b'. By the triangle inequality, a<b'+y. Thus, a+b<b'+y+b.
- 2-flush against the shortest sides beats 1-flush against the longest side.
[We realized Thursday 29Apr that this proof below is not correct. However, we know it is true simply by plotting the relationships in Mathematica.] Because we have a right triangle, we know that a'<1. Hence, a'(1-(a+x))<1-(a+x) a'-a'(a+x)<1-(a+x) a'+a+x<1+a'(a+x) From our area equations ½(1)(h)=½(a')(a+x), so h=a'(a+x). Thus, a'+a+x<1+h. By the triangle inequality, b<a'+x. So, a+b<a+(a'+x)<1+h. Hence, a+b<1+h.
Since 2-flush against the shortest sides beats both other 2-flush possibilities, we are able to conclude that 2-flush against the shortest sides wins in every case.