Just email the TA (irving@cs.stanford.edu) 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.

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

- The CGAL manual.
- The CGAL Qt_widget which provides the interface between CGAL and Qt.
- The Qt manuals.

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

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.

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

3 3.0 0.5 (1.0+2.0*t-1.5*t^3,1.0+2.0*t-1.5*t^3) (2.0+3.0*t,1.1+2.0*t-165*t^3) (0,0)

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.

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:

`int polynomial::rroots(double roots[]);`- Computes all real roots of the polynomial, and returns the number n of roots. The roots are stored in roots[1]...roots[n]. The roots are not sorted
`polynomial polymat_det3(polynomial mat[3][3]);`- Computes the determinant of the 3x3 matrix mat whose entries are polynomials

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:

` ``/usr/class/cs268/hw2-template/`

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.

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 t_{0}, the flipped edge e' that replaces e at
t_{0} is certified by the same InCircle test (with opposite sign). One of the
roots of this test will be t_{0}. 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 t_{0}, but t_{0} 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.