Project 3: Efficient Golf Inc.

In this project, you will get to design golf courses that mirror the great golf courses designed by the great course designers. You run the Efficient Golf company, and pride yourself on being able to design courses according to any specification.

Your most recent customer has provided you with an unusual challenge. She is the Prime Minister of Microland, a very small country located on a remote island in the South Pacific. The country is very wealthy due to it's offshore oil, but it has very little land. The Prime Minister wants to build a championship golf course that uses the least area. In order to achieve this goal, the Prime Minister is willing to allow fairways to intersect, as long as the greens and tee-off points do not intersect other greens or fairways. For reasons of playability, no part of the course may belong to more than two different fairways. (By the way, if you're successful here, the President of Nanoland also wants to build a golf course. He is willing to allow an arbitrary degree of fairway overlap for his course.)

Clients generally insist on giving you the exact specifications of each of the eighteen holes (more on the specification later). Based on these specifications and the client's optimization criteria, you are expected to come up with the best design that minimizes the client's cost function.

You will write a computer program that reads in a course specification, and generates a course layout (defined below). The layout must be correct. For the Prime Minister of Microland, correctness means no overlap of greens or tee-off points with any other part of the course, and at most two fairways covering any given point. (For the President of Nanoland, this last condition is removed.) Correct solutions will be ranked according to the appropriate cost measure.

The course is specified by a global width parameter $w$, and a sequence of 18 hole-specifications. A hole specification consists of a par-value $P$ (3, 4, or 5) and a sequence of $P-1$ points. The first point defines the tee-off point. The final point $F$ is the hole, and the green is implicitly defined as a circle with center $F$ and radius $w$. Intermediate points define the fairways, which may have dog-leg shaped bends etc. The unit of measure is meters.

For example, the following specification is based on The Bull golf course. (Actually, the specification below is scaled by about 80% relative to the real course.) The coordinates are all double precision numbers. We adopt the convention typical of graphics displays that the $y$ coordinate increases downwards.

14.0
4 376 860 318 660 303 563
4 246 557 254 746 192 832
3 168 801 207 654
5 122 657 135 433 69 331 67 282
4 94 236 276 192 322 76
3 358 114 342 243
4 381 339 411 167 403 85
5 438 33 525 206 524 347 461 360
4 431 360 446 582 444 682
4 526 771 490 546 533 442
4 663 414 807 522 793 583
3 838 639 738 786
5 767 804 899 651 913 521 888 456
4 850 321 1025 426 1038 540
3 1064 546 1129 442
4 1154 396 1122 225 1033 131
5 982 136 807 272 732 368 674 381
4 581 418 564 611 572 749

The following diagram illustrates a par-4 hole. $P1$ at $(0,0)$ is the tee-off point. The fairway makes a 90 degree left turn at $P2$, and the green is centered at $P3$. Each line ($P1P2$, $P2P3$ etc.) defines a pair of parallel fairway boundaries each $w$ units from the line itself. When the fairway makes a turn, say from $P1P2$ to $P2P3$, the corner points are where the corresponding boundary lines intersect. You may assume that holes are not self-overlapping, such as a hole that curves around and crosses itself. (How does one precisely define ``self-overlapping''?)

Your programs output a course layout, in the same format as the input course layout. (We will check the total area of the course to make sure you haven't changed the geometry!) While the input to your program will typically be a set of nonoverlapping holes, your program should also accept inputs that are overlapping. This way, we will be able to run groups' programs in succession to see if the combined efforts of two groups might do better than each group alone. It will also allow you to evaluate how sensitive your methods are to the initial positions of the holes in the input file.

To measure your layout, a rectangular bounding box will be placed around the entire course. (In Microland, all real-estate is sold in rectangular parcels.) Your score is the area of this bounding box divided by the total area of the holes. The bounding box has edges parallel with the axes; you may need to think about how to orient your placement accordingly.

Here are some things to think about:

1. What is a lower bound on the Prime Minister's course area, as a fraction of the total (nonoverlapping) course area?
2. Does this look like an intractable (e.g., NP-hard) problem?
3. Are there some simpler special cases? For example, what if all of the holes are perfectly straight?
4. Even though the fairway as a whole is not convex, each piece of the fairway is a convex quadrilateral. Thus you can use algorithms from computational geometry that apply only to convex polygons, such as algorithms for intersecting polygons.

We'll supply a standard set of 18 holes. Each group will be asked to provide a set of 18 holes too. For the tournament, your programs will be run on both previously-seen and unseen sets of holes. The course-verifier and sample courses can be found here. Note that the course-verifier is stand-alone software, and is different from the simulator used for projects 1 and 2. Your code will also be stand-alone software.