Difference between revisions of "MTH301 Math Research"
(→Proof that 2 sweeps don't suffice for all figures) |
m (→Proof that 2 sweeps don't suffice for all figures) |
||
Line 102: | Line 102: | ||
====Proof that 2 sweeps don't suffice for all figures==== | ====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. | + | 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. |
Revision as of 09:31, 20 February 2010
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
Resources
Hypotheses and Theorems and Lemmas
28 Jan 2010
For Arbitrary Shapes
- 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
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!)
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.