COS 226 Programming Assignment 7 - Checklist


In a case where many lines separate a query pair, you are only responsible for outputing a single such line (which one is up to you).

If you do choose to use some other method than the search tree approach described in the assighment you must give a good justification in your readme as to why you chose that approach.

Please note that we will be testing the correctness of your programs on many more queries than the ones given in the files in the assignments.. You will notice that the above files give more and more line segments, but each of them only contains one or two sample queries at the end. Since one of the biggest issues of geometric computing is to correctly handle the many cases which arise, you should make sure to test your program correctness on many more queries.

At the end of the construction of your data structure, your program should report the number of external nodes in your tree, and the average external path length. (The path length to a particular external node is the number of internal nodes which are encountered when walking down the tree to that external node).

For each of the pairs of query points, you should print a line of output which describes a specific line which separates the two points, or else states that no such line exists.

Your readme file for this program should contain the following:

  • A high-level description for the design of your algorithm, what influenced your decisions, and any performance issues.
  • A table of the number of external nodes, and average path length of these nodes for various size input files. Discuss the growth of these numbers.
  • A (brief) discussion of any vulnerability which your program has as far as degenerate cases or numerical inaccuracy.
    • Possible Progress Steps:
  • Successfully read the input lines.
  • Write a program which creates a PostScript diagram of the input lines.
  • Write a brute force routine for answering queries (i.e. one which compares the query points individually to each input line). Although this will not involve preprocessing the input lines, it will force you to implement some of the necessary geometric primitives.

    • Testing Your Program: As mentioned above, you should test your program on many more interesting inputs and queries than the ones we have provided. In testing correctness of your method, you may want to debug by also comparing your results to the (more expensive) brute force method for answering queries.

    cos226 Class Page
    rs@cs.princeton.edu
    Last modified: April 8, 2001