Due Thu March 22, 2001

Extended to Fri March 23 at 10pm

Your code must make **only one** call to STL's sort() per convex hull
and have overall complexity *O(N log N)*. Everything else is up to you.

Your implementation must show good programming style and be reusable.

Your program must check the following ** formal condition**
that addresses all of the above concerns.

One potentially helpful fact is that if the two convex hulls are within 1 mile of each other, it is also the case that at least one the points on the boundary of one of the convex hulls is within 1 mile of the other convex hull.

You are to write a program that, given the *2N* locations,
can determine in *O(N log(N))* time whether you should warn all
skippers. Your program may terminate as soon as it processed enough data
to conclude that the the convex hulls are closer than one mile. For example,
when a shark is found half a mile from a yacht, the program may signal
"shark-proximity warning" and stop so that all skippers can be warned right
away.
For complexity analysis, you can assume that the boundary of the convex hulls
of both the yachts and sharks contain *O(N ^{1/2} )*
vertices.

- Finding the distance between a given point and a given line segment
- Determining whether a given point is inside a given convex polygon

C X Ywhere C is a character (`Y' for Yacht or `S' for shark) and X and Y are real valued coordinates measured in miles. The real numbers will be in the range from -100.0 to 100.0. Having too many lines is not an error, but everything beyond the

sample input files are available

The command-line argument
`-Inputfile`

will indicate the name of the input file. If no
input file is specified, the file `elvis.txt`

should be used.

Based on those inputs, your program must generate exactly one of the following messages to standard output:

- ``
**A shark is too close:**'' if at least one shark is closer than one mile from the convex hall of yachts. This message must be followed by the shark's location. (X location then Y location) Example:

`A shark is too close: 3.4000 -2.4554`

- ``
**A yacht is too close:**'' if at least one yacht is closer than one mile from the convex hall of sharks. This message must be followed by the yacht's location. Example:

`A yacht is too close: -8.11 -2.4010`

- ``
**No warnings**'' means that neither of the two warnings are in effect.

- ``
**Error:**'' indicates that something went wrong and the program could not reliably complete. This might be due to an input error or some other error condition. This message must be followed by an explanation of the error. See the section below for a list of errors for which you need to check. You may use any descriptive message here.

For the first three cases, nothing else should be printed to standard output
and the program must `exit(0)`

. In the case of an error the
program must print an error message to standard output *and* to the
standard error, then terminate with `exit(1)`

.

It is possible that it may be appropriate to print both message 1 and message 2. However, you are to print out just one of them (your choice).

- Unexpected first line (normally, it must have one integer number)
- Insufficient number of lines (fewer than implied by the first line)
- Coordinate out of range, (value not between -100 and 100 inclusive).
- Invalid first character (First character is not a Y or an S)
- Invalid line (Line is not in the "
`C X Y`

" format). - Input file does not exist.
- There were 2N lines but not N sharks and N yachts.

- An outline of your algorithm which steps through the major activities of
your code which lists the complexity of each of these stages. For most
programs there will be 5-10 major activities (read in the input, sort, print
out the output, etc.) which can be identified. In addition, for the actual
check to see if the convex hulls are within 1 mile of each other, they would
like you identify break this down into its various components. (Computing the
convex hulls, checking to see if a point lies within the convex hulls, etc.)
This outline is to be written in a text file called
`algorithm.txt`

Remember, your implementation should have

*O(N log(N))*runtime. - An empirical study which times your algorithm on worst-case inputs of
varying size. For these cases you should create inputs which have exactly
ceiling(N
^{1/2}) vertices in the boundary of both convex hulls. Further, you should be sure that these are reasonably close to the worst-case inputs. You are to provide a postscript file named`worstCase.ps`

in the directory with your program. It should be a one-page graph showing how the run-time varies with N.**(The graph must also include your name and unique name!)** - A set of ten test cases. Five of them must be test cases which you used
to generate your run-time graph (although you may have used more test cases...) These are to be called
`runtimeTest.x`

where x varies from 1 to 5. The other five must be*non-error*test cases which show your program will get the correct answer even for ``corner cases.'' They are to be called`cornerTest.x`

where x again varies from 1 to 5. All of these files should be in a subdirectory named`TESTS`

and none of these tests should contain more than 10,000 points. Note: for the corner cases you are simply supplying test cases*you*believe do a good job of testing your code for correctness.

**Your need to create your own testcases that are different from other students' testcases.**

Note that the very
operation of receiving data typically takes at least linear time, and
*N log(N)*
is a "near-linear" function. Therefore, if your implementation requires
*O(N log(N))* time, you can say that even in the worst case you can
process radar/sonar data almost as fast as they arrive.

More hints will be posted as handouts

- Complete code to the autograder, as in project 1. The
command
`make`

should build your program. The command`make clean`

should remove all temporary files and the executable. Your executable should be called`findSharks`

- The annotated outline of your algorithm in a file called
`algorithm.txt`

. - A postscript graph of your empirical testing showing that the
runtime does not grow significantly faster than N. This should be
called
`worstCase.ps`

- Ten test cases that you generated should be in the subdirectory TESTS and named as described above.

Note that in the overall worst-case, the boundary of the convex hull of
*N* points can contain all of them. However, for the purpose of this
project, we assume a "reasonable" distribution with fewer points lying on
the boundary of the convex hull. Therefore, we consider worst cases under
this assumption.

- You have deleted all .o files and your executable(s), e.g., by typing make clean.
- Your makefile is called
`Makefile`

`make clean`

actually does remove the executable and the tmp files (such as .o files)- Typing the command
`make`

will generate an executable called`findSharks`

- You don't have any unneeded files or other junk in that directory or any of its subdirectories.
- Go to one level above the the directory with your code (and makefile,
etc.). type
`/afs/engin.umich.edu/class/perm/eecs380/bin/submit380 2 DIRNAME`

where DIRNAME is the name of the directory in question. The program will verify that you wish to turn your code in, and that's it.

Also note that if you generate a large number of sharks and a large number of yachts in the square [-100,100]x[-100,100], then most likely, the convex hulls will intersect. You need to come up with ways to generate configurations where convex hulls can be far apart. Otherwise, you will not be able to empirically evaluate worst-case performance and your tests for correctness will be weak.

Finally, you may find it difficult to generate test cases of size N with
exactly *ceiling(N ^{1/2})* vertices in the boundary of the
convex hull. Our suggestion is to use a circle and place the needed
points on the circle and then place the remaining points well inside of
the circle (maintaining the required spacing). This part is not supposed
to be hard, if you have problems figuring out how to do it, ask.
Discussions (but not code) on this topic are welcome on the newsgroup.

`purify`

and `gdb`

.
We've been told that all enrolled 380 students have been given access to
Purify. (Thanks Ken!)
- Consider
*N*dots that are (uniformly) randomly placed inside a given circle. What will be the average percentage of dots that are in the boundary of the convex hull? Why? (The percent seems to drop as*N*increases, but at what rate?) - Same as above but for a square.

These animations (implemented in Java) may illustrate how Graham's scan
works...some aren't exactly the same as in the handout (i.e., using the
topmost point as
P_{0} instead of the bottommost point, etc.), but they're pretty close:

From Alejo Hausner at Princeton: Graham, Graham Scan

From Mandar Gokhale at U of Illinois: GrahramAlgo

From Connie Peng at U of Maryland (allows you to specify the points): convex hull_anim

Thanks to Brett Allen for finding those.