Program Submissions

Just email the TA ( a tarball of your source and a README file. Please state in the README what the TA needs to do to compile it and where he should expect to succeed in compiling it (if it only works on some of the leland system types) --- in addition to whatetever else is required in the problem set assignment.

CGAL and Qt

We recommend that you use CGAL and Qt for your programming project. The information below should be enough to get you started.


The manuals can be found on the internet.:

Writing Your Own Programs

As the CGAL libraries use C++ template classes heavily, the error messages can sometimes be dauting. Come and see the TA for debugging sessions.

Homework 2 Submission

You should submit your source code and a README file. As before, submit by emailing the TA ( a compressed tarball of your sources, makefile and README.

User interface

You can assume that the data is input from a data file; you do not need to design an interactive interface to input the disks. However, you may still want to implement a simple interface to read in the input data file, to control the animation, and to draw the animation.

Input data format

The following is an example of the input data format -- note that general polynomial trajectories are allowed as input:

    3 3.0 0.5

In the file, the first line describes the number of objects, the size w of the box (the coordinates for the box are [0, w]x[0, w]), and the radius of the disks (when the radius is 0, then they are points and you do not need to detect collision between the objects).

Each line defines the motion of one disk as (x(t), y(t)). You may assume that the input data is valid, i.e. the disks are inside the box and are disjoint.

Polynomial library

We provide a library for manipulating polynomials. In addition to the normal arithmetic operations you would expect for polynomials, an object of the class polynomial has two interesting methods:

Note that although the InCircle test was defined in class as the determinant of a 4x4 matrix, there is a simple way to reduce it to the determinant of a 3x3 matrix.

The library and a simple example on how to use it can be found in the directory:


on the Myth machines. The template also contains animation code. If you build it and run it on a data file it will compute the Delaunay triangulation for the initial state, and then animate the points without updating the triangulation or handling collisions. That should help to start out.

Please do not modify the polynomial solver library. Make your own subclass if you want some additional or modified features, or write your new code in files with different names.

Tips, warnings, assumptions

Assume no degeneracies in the initial data.

The curse of floating point operations

An InCircle test output is given by the sign of a 4x4 determinant (one row per point involved in the test). If the coordinates of the points are linear functions of time, the determinant is a polynomial of degree 4. Hence, it has several roots.

If an edge e is certified by an InCircle test that fails at time t0, the flipped edge e' that replaces e at t0 is certified by the same InCircle test (with opposite sign). One of the roots of this test will be t0. You will run into difficulties with numerical inaccuracies here, as you can expect that the root in question, as found by the numerical solver, will not be exactly t0, but t0 plus or minus a small epsilon. Beware.

Try to follow the primitive, predicate, combinatorial structure idea when structuring your code. Isolate the numerical code in a few predicate functions and make the rest of your code independent of the details of their implementation.