1728. Roofing It

Bill Eaves owns the Shingle Minded roofing company which is a sub-contracting firm specializing in putting roofs on buildings. Often, Bill will receive a design for a roof from some young hot-shot architect which, though it may have some aesthetic appeal, is totally impractical. In these cases, Bill will begin negotiations with the architect and the client to find a simpler design. Bill’s only concern is that the roof be convex, to allow rain, snow and frisbees to roll off easily. The architect’s main concern is that the maximum height between his original roof and the compromise roof be as small as possible. The client’s main concern is to get out of this meeting as soon as possible and get back to watching TV.

The architect’s plans for the roof come in the form of a series of n points (xi, yi) specifying the outline of the roof as seen from the side of the house. The roofs are always symmetrical, so the architect only shows the front side of the roof (from its start at the front of the house to its peak). Once Bill gets these plans and a decision is made on how many sections the convex roof should have, he must decide how to place the sections so as to 1) make sure that all the original (xi, yi) points lie on or below the new roof, and 2) to minimize the maximum vertical distance between any of the original (xi, yi) points and the new roof. All sections must lie on at least two of the initial points specified by the architect. An example is shown below. On the left are the initial points from the architect. The next two pictures show an approximation of the roof using only two sections. While both of these are convex, the second of the two is the one which minimizes the maximum distance.