Computational Geometry, Spring 1999 - final assignment (applied track)

Last updated on: August 2, 1999.

2/8/99 - Two more input sets of medium size:
    input_grid100, command_grid100, output_grid100.
    input_diagonal20, command_diagonal20, output_diagonal20.
    Use radius=10000 for both sets.
I would like to remind you that:
    (a) You should submit a "readme" file that describes your algorithm, the files, etc.
    (b) You may provide one input set for the contest.
29/7/99 - Here is another set of files to test and time your program, with 100 points, 10 polygons, and 100 commands:
    input_time100, command_time100, output_time100.
    Run: "main 10000 input_time100 command_time100 output", and compare your "output" file with "output_time100".
    And here is a larger version, with 1000 points and 1000 commands:
    input_time1000, command_time1000.
    Again, use a radius of 10000.
27/7/99 - Here is a set of files to test your program:
    input_test, command_test, output_test.
    Run: "main 120 input_test command_test output", and compare your "output" file with "output_test".
27/7/99 - Fixed a bug in "main.C", in case of a vertical edge (thanks to Ishay Pnueli). Please download the new version.
8/7/99 - Fixed bugs in "main.C". Please download the new version.

This page contains the frame program for the final assignment in the course. You will also find here updates and FAQs, so stay tuned.
If you have any questions regarding the program or the contest, please email Chaim Linhart: chaim@math.tau.ac.il.
On questions regarding LEDA or CGAL, please contact Iddo Hanniel: hanniel@math.tau.ac.il.
More information can be found at the course homepage.


The Frame Program

First, download the following files:

  • main.C - the frame program, that reads the input, calls the algorithm's functions, and displays the results.
  • algorithm.h - defines the basic data types you should work with, as well as the interface of the "Algorithm" class that you should implement.
  • algorithm.C - a dummy implementation of the "Algorithm" class. You should change this implementation by a corrrect and efficient one of your own.
  • makefile - a simple makefile to build the program.
  • input_file, command_file - sample input files for the program. The actual input files in the contest will be much larger.

    Next, compile the program by running "make" (on valis).
    The program receives the following command-line parameters:
      "main radius input-file command-file [output-file]", where:
    radius - the radius (an integer!)
    input-file - file with points and polygons
    command-file - file with commands
    output-file - file to write solutions (optional)

    Now run the program: "main 3 input_file command_file" (make sure to set the DISPLAY variable if you are working on a remote machine).
    If all went well, you are now ready to implement your own "Algorithm" class.
    You can find all the technical details in the source files.
    Good luck!