MTH301 Math Research

From CSclasswiki
Revision as of 10:02, 13 March 2010 by Orourke (talk | contribs) (For Arbitrary Shapes)
Jump to: navigation, search

Welcome to the MTH301 Math Research Page

How to edit Wiki pages: See the Wikipedia editing cheat sheet.

Participants:

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.

Resources

  • My initial beamer presentation is here.
  • 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.

parallelogram
Minimum Perimeter Enclosing Parallelogram
  • 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:

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

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!)

hairpinx1
Hairpin, 120 deg, isosceles: x=1
hairpinx15
Hairpin, 120 deg, x=1.5
hairpinx2
Hairpin, 120 deg, x=2
hairpinx4
Hairpin, 120 deg, x=4
hairpinx10
Hairpin, 120 deg, x=10

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...

hairpinx1
Hairpin, 30 deg, isosceles: x=1
hairpinx1
Hairpin, 30 deg, x=1.1
hairpinx1
Hairpin, 30 deg, x=1.2

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.

Today's favorite image!

flush function
Flush Function, Overhead View

Here is the result of using ContourPlot[ FlushFunction[] ]:

flush function
Flush Function, ContourPlot

I solved the equation for b in terms of a. Here it is in raw form. Did not try to simplify or reorganize.

zero equation
Zero Curve

Beamer Skeleton Files

Here is a .zip file containing everything needed to run off the beamer skeleton we created today:

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:

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 a parallelogram.
3 sweeps
Another example that seems to need three sweeps
  • This example makes me realize that there is a hypothesis close to our original falsified hypothesis that we haven't yet killed:
    • Hypothesis: The optimal sweeping of any convex polygon uses only two sweeps.