Project 2: Setting the Table

The Elaborate Table Company (ETC) has hired you to help them with their table designs. More precisely, ETC already has various table designs in mind, and your job is to figure out how practical the table is for serving meals. Your job is made difficult by the fact that the chief designer at ETC, Umberto Ego, has come up with some wildly inventive and unusual table shapes.

You need to place seats around the table, and cutlery, crockery, glassware, and other items on the table according to certain rules. While the rules are designed to make eating feasible, they do not require strict adherence to conventional table settings. For example, you do not have to place knives and forks on opposite sides of the plate, as long as all elements do not overlap, and are within reach of the person sitting at the table. There are some other constraints too, described below.

Umberto's tables are polygons that are simple, without holes, but not necessarily convex. You are expected to place seats around the exterior of the table, i.e., outside the perimeter of the table. A seat is a circle with diameter of 50cm. Seats may not overlap with each other or with the table.

For each seat, there must be a corresponding place-setting near that seat. A place setting consists of:

• A circular plate with diameter 35cm. The plate must be within 20cm of (some part of) the corresponding seat. (Note that this will require both the plate and the seat to be close to the table's perimeter.)
• Two knives, two forks and two spoons. The three large implements are modeled as rectangles of size 30cm by 2cm, while the three small implements are modeled as rectangles of size 20cm by 1.5cm.
• Two round glasses, of diameter 9cm and 7cm respectively.
• A triangular napkin, which has two 10cm sides that include a right angle.

All place setting elements must be entirely within 100cm of the center of the seat, and may not overlap with anything else on the table, or with the table perimeter.

To avoid confusion among the diners:

• Each item must be closer (measured from the nearest point) to the center of the corresponding seat than to the centers of all other seats.
• Each item must be the closest (measured from the nearest point) to the center of the corresponding seat among all identical items on the table. For example, the small fork for seat $s$ must be the closest small fork to seat $s$.

In addition to the items mentioned above, there must also be placed on the table:

• One rectangular bread board (50cm by 40cm).
• Salt and pepper shakers made of glass (circles of diameter 4cm).
• A salad bowl (a circle of diameter 50cm).
• Two glass wine bottles (circles of diameter 8cm).
• A rectangular glass butter dish (15cm by 5cm).
• A round glass water jug (diameter 25cm).

Each of these items must be within 100cm of some seat, so that it can be passed to other diners. Again, these elements cannot overlap with anything else on the table, or with the table perimeter.

All glass items must be at least 15cm away from the table perimeter for safety.

You will be given the geometry of the table, and you will need to fit as many settings as possible around the table. You will score one point for every setting that you manage to fit. There is no requirement that each diner have an identical layout of their implements. However, if you can achieve a symmetric solution, you score an extra half-point. By symmetric, I mean that the place-setting elements for a seat and the corresponding seat, taken together as a geometric entity, is congruent to that for every other such entity. (The position of the table perimeter is not important.)

Some initial table designs will be provided. Each group will also be asked to come up with an interesting table design, to give us a variety of shapes.

For the tournament, your programs will also be run against tables you have not previously seen.

Some things to think about:

• You have a variety of constraints to deal with. Which are the hardest ones to satisfy? Does it depend on the table?
• Is finding the optimal solution to the problem NP-complete?