Brief answers to the midterm questions:


1) Here you can claim that your exterior point X can see a vertex V of the hull. You want to do a rotating sweep til you hit a tangent to the polygon. If you cant see the adjacent edge to V, something is in the way. Let the first vertex that you hit (that also obstructs the edge), become V. Now continue your sweep. This is a finite process. Eventually nothing will be in the way.


2) (a) Assume the polygon with max area is not convex. Find a pocket and invert it. This cannot cause any intersections and increases the area. Contradiction.
(b) Assume that the polygon with max area is convex, and that it is not equilateral. Then there exist two successive edges that do not have the same length. Together with a diagonal they form a triangle. Slide the apex parallel to the diagonal until the triangle is isosceles (and our two edges have same length). So far we have not modified the area, but we have reduced the perimeter. Now push the apex out until the perimeter length is restored. We have increased the area. Another way to think of this is to slide the apex along an ellipse whose loci are its two adjacent points on the hull. This preserves the length of the two edges. The maximum area obtained is at a symmetric position.


3) First prove that the line must pass through the convex hull of the points (easy). Second, only points on the hull can have max Y-distance to the line, so we only care about those. ...Why? Suppose that you guess the right slope. The point with max y-distance is found by sweeping a parallel line until you are just tangent to the hull. Third, we can just look at slopes parallel to hull edges. ...Why? Suppose that your tangent just touches vertices on each side. Then you can rotate both in some direction and reduce the y-distance between them (by making them more horizontal). An exception occurs when the two vertices of support are covertical. Then the slope doesn't matter, so we might as well rotate till we hit an edge.
After this, a nice method is to use the rotating calipers and at every critical position (i.e. every time a caliper is on a hull edge), measure the Y-distance between the two calipers. Wherever we find the minimum, position your line right between the two calipers, with same slope.