Plane Geometry, Convex Shapes
Convex Polygons
|
A polygon is a chain of line segments
that never cross each other,
and the last endpoint of the last segment is the first end point of the first segment.
In other words, the chain is closed.
The triangle and rectangle are two examples.
A convex polygon has no inlets or bays.
Formally, whenever two points are contained in a comvex shape,
the entire segment connecting those two points is contained in that shape.
When the shape is a polygon, there is an equivalent definition.
The polygon is convex iff every interior angle ≤ 180°.
Let's prove this in both directions.
A larger angle implies an inward bend.
Place a point on either side and draw a segment that cuts across the bay,
hence part of the segment is outside the shape.
Conversely, let the segment from p to q prove that a polygon is not convex.
Let x be the point where the polygon first intersects the segment pq,
and let y be the next point of intersection.
Thus the segment xy is outside the polygon.
Trace the polygon as it moves from x to y
and let v be a point on this path that is farthest from the line xy.
If v is not a vertex then it is part of a line segment that is parallel to xy.
Move along this segment until you find an end point and call it v.
Now v is a vertex whose adjacent sides form an angle that exceeds 180°.
| |
|
Convex Hull
Given a bounded shape S in the plane, or in n space for that matter,
the convex hull about S is the intersection of all the convex sets containing S.
Prove that the intersection of convex sets is convex; hence the convex hull is convex.
Let's do a simple example.
Arrange 4 points in a square: at 0,0 0,1 1,0 and 1,1.
The closed square spanned by these 4 points is the convex hull.
It's obvious, but let's prove it.
The square is convex, so the convex hull is contained within this square.
Since the hull contains the origin and 0,1 it contains the segment that joins them.
Similarly, it contains all 4 sides.
Finally, fill in the square, like you are coloring in a coloring book; and don't go outside the lines!
Each point inside is part of a segment that contains to border points, which in turn are part of the convex hull.
Thus the entire square is the convex hull.
You can often (though not always) apply this strategy, even in n dimensions.
Find the extremal points of S, draw lines between them, fill in the lines with faces, etc.
Linear Transformation
Apply a linear transformation f to n space, and the convex hull about f(S) is f applied to the convext hull about S.
This is because the image of a line segment is a line segment, and the preimage of a line segment is a line segment.
Convex sets correspond, and intersection carries across.
Note that there are other functions that map lines to lines,
but a linear transformation is the most obvious, and the most practical.
Area spanned by a String
You have one meter of string.
You want to lay it out in the plane so that the convex hull
that surrounds it has the largest area.
You can cut it into pieces if you like, but you have to put the pieces
back together to make a connected set.
In other words, you can't chop it into 4 pieces and spread
them a mile apart to span a square mile.
So what is the best shape?
A straight line has no area - that's no good.
How about two segments that form two legs of a triangle, like the letter V?
Pivot one of the two legs and the best angle will be 90 degrees.
Any other angle gives a smaller altitude and the same base in the formula bh/2.
So 90 degrees it is.
From here some calculus shows the legs should be equal, each half a meter,
giving an area of 1/8.
Now cross the two segments like the letter X.
As shown above, an angle of 90 degrees is best, like the + sign.
And the two lengths are equal.
This makes 4 small right triangles,
each having area 1/32, so the area is still 1/8.
How about the letter Y?
Make the three segments equal, each having length 1/3, and make the angles 120 degrees.
This spans an equilateral triangle with area sqrt(3)/12 = 0.1443.
That's better than 0.125.
Finally, use the letter C as your inspiration,
but stretch it into a perfect semicircle with radious 1/π.
The enclosed area is 1/(2π).
I don't have a formal proof, but I'm pretty sure this is the best you can do.
Volume spanned by a String
What about 3 dimensions?
The convex hull is created by stretching shrink wrap around the shape.
What is the largest volume?
Connect 3 segments of length 1/3 at the corner of a cube.
The shape is a right simplex with volume 1/(27×6) = 0.00617.
Connect 4 sticks at a central point, like a methane molecule.
Use some geometry to find the volume of this shape.
For the moment, let the edge of a tetrahedron have length 1.
The base is an equilateral triangle.
The distance from its corner to its center is sqrt(1/3).
The altitude has height sqrt(2/3).
The volume is bh/3 = sqrt(2)/12.
The distance from the center of the tetrahedron to any of its 4 corners is sqrt(6)/4.
The total length of the 4 sticks, from center to corners, is sqrt(6).
Scale the shape so that this length is 1.
This divides volume by sqrt(6) cubed, giving
sqrt(3)/216 = 0.00801.
this is clearly better than 1/162.
Draw a semicircle in the plane and stand a goal post up at one end.
for completeness, draw in the other half of the circle.
The convex hull is determined by lines joining the top of the post to all the points around the circle.
I want to convince you that this is really the same as the cone with the post in the middle.
Let the top of the post be the origin, pointing up the z axis.
A linear transformation fixes the xy plane, and slides each plane above and below
to the left and right proportionally, according to the z coordinate.
Our circle slides over, and the goal post stands on the edge where it belongs.
This linear transformation maps lines to lines, and the transformed cone becomes our convex hull.
Thus the volume is the area of our semicircle times height divided by 3.
This is maximized when the semicircle has length 2/3 and the post has height 1/3.
The volume is 2/(81×π), or 0.00785.
This is surprising; I really thought it would come out better than the tetrahedron.
The same cone argument applies if we put the goal post anywhere along the semicircle.
Erect two goal posts at the ends of the semicircle.
At each level, the cross section starts at one post, travels a quarter circle,
moves in a straight line towards the other post, and runs a quarter circle to that post.
Combine the quarter circles and find the volume of the cone shown above.
This is πr2h/6.
Then add the wedge, which is r2h/3.
The best solution has r = 2/(3π) and h = 1/6,
giving a sad0.00643.
Join 3 quarter circles together at a point, with angles of 120 degrees,
so that they cradle a hemisphere.
Of course the convex hull is not a hemisphere;
each cross section is an inscribed equilateral triangle, rather than a circle.
Adjust the volume of the hemisphere by this ratio and get
4×sqrt(3) over 27π3 = 0.00827.
This is the best I have come up with so far.
I conjecture that the best in n dimensions is n quarter circles joined at a point and forming equal angles,
so as to cradle a hemisphere in n dimensions.
This seems to hold true for dimensions 2 and 3.