Project 3: Piece of Cake!

You work for a catering company that specializes in customization of food portions for patrons. The company allows a customer to order a piece of cake, specifying exactly how big the piece should be, in square centimeters. The customer then receives a piece that is (hopefully) close to the requested size. The shape of the cake piece is not important, except that it must be a single piece that fits on a plate of diameter 25cm.

Behind the scenes, the cake is a large rectangle with proportions 1:1.6. The shorter linear side length L of the rectangle is a parameter. Each patron may ask for a piece of cake anywhere between 10 square centimeters and 100 square centimeters. An event is catered in such a way that the total area of all requests is close to but not larger than the size of the cake. You are told the list of requested sizes before cutting commences.

The catering company has a large robotic device with a knife that can cut the cake in a precise fashion. The machine works by performing a straight linear cut from one edge of the cake to another. The start point of the first cut is chosen by you anywhere on the perimeter of the cake. After that, the start point of a cut coincides with the endpoint of the previous cut. You get to choose the endpoint of each cut, anywhere on a different face of the cake from the previous endpoint. Once you've finished cutting, the cake will have been partitioned into a number of polygonal pieces. You then map customers to pieces based on their size preferences.

Customers are tolerant of small differences of up to d percent of their specified area, where d is a parameter. If you deliver a piece within d percent of the requested size, there is no penalty added to your score. However, if the piece differs from the requested size by p>d percent, you accrue a penatly of p. Your primary goal is to minimize the aggregate penalty. A secondary goal, used to break ties on the primary goal, is to minimize the total length of the cuts, since shorter cuts means that the cutting process is more efficient.

A configuration specifies values for L and d along with the list of request sizes. We'll ask groups to come up with ``interesting'' configurations during the project. The simulator will also be able to generate a random list of requests for a given L value, where each request is of size chosen uniformly from [10,100], and the total size of all requests is just below the area of the cake.

The simulator will interact with your code and do some basic error checking. The simulator will disallow choices that do not meet the project specifications, with appropriate consequences depending on the infraction. The subproblem of finding the smallest circle around a set of points is an interesting one, and may be helpful for figuring out whether a piece of cake fits on a plate. You can read about it, and potentially use some publicly available python code for this subproblem.

Some things to think about:

• Are the pieces guaranteed to be convex? Why?
• Is it more difficult to process many small pieces or fewer large pieces?