- HW 1 : Jan 15
- Read chapter 1 of the text book. Read pages 1-12 from Dr. Mount's notes.
- Homework 1: Cauchy Schwarz, Triangle Inequalities, Definition of dot and cross products.
- Not to be graded: Implement your own dvector and dsegment classes.
- Extra Credit: Implement a d-dimensional determinant calculator which works on d+1 d-dimensional points and returns orientations. First use homogenious coordinates to turn these points to (d+1)x(d+1) matrix, whose determinant you seek. Then use metaprogramming to evalue this determinant without run time function calls. You can assume d is a small constant (< 10).
- HW 2 : Jan 27
- Read Lectures 1-4 of Dr. Mount's notes.
- Homework 2 is out.
- HW 3 : Due Feb 12, before class.
- HW 5 : Due March 17th before class
- Delaunay triangulation project : Due date: April 15th
- Goal: Compute Delaunay Triangulation in C++.
- Your job is to write source code that will make this cpp file compile and run. For an example you can look at triangle++. The source code should be sent to me using a .tar.gz file, like this one. Your source code should use predicates.c from Jonathan, but nothing else. I want you to use the dpoint.hpp class that you used in your last assignment. You can pick any algorithm that you want to code, but its running time should be bounded by O(nlogn) in the expected or worst case. You can look into the paper by Blandford, Blelloch, Cardoze, and Kadow for representing your mesh (without the compression, unless you want it). You can consider implementing D&C, incremental algorithm or gift wrapping algorithms. For point location, you might want to use STANN. If you want the fastest triangulator possible, consider the divide-and-conquer algorithm described in the paper by Guibas and Stolfi. You might want to read this first.
- Language: Only C++
- Geometric Predicates : predicates.c
- Input: One sample data file input is included in triangle++.tar.gz file in the data directory. There are many .node files here. You can easily extract the points from .node files by writing a small script in any language.
- Prize: Borders gift card of 25 dollars, if you can beat triangle++ in speed AND your code is the fastest among your peers.
- HW 6 : Due April 14th before class.