CS661 Geometric Algorithms: Project Options

CS661 Geometric Algorithms: Project Options


Your project is to implement and test any one of the algorithms from the problems below.

There is a template for your report that you should read carefully. Then you can cut and paste into
a copy of it and your formatting/sectioning will be taken care of.

Project Report Template

Project possibilities to choose from:

One project is to implement and test the line-sweep algorithm for finding intersections among N line segments in the plane. It should handle all the special/degenerate cases that the book's algorithm does and any others you can think of if you can. You are welcome to try things differently than the book, but you do not have to. This first project is mostly to get you thinking about the complexities involved in implementation at various levels of a geometric algorithm. You could choose some other kind of height-balanced tree than the AVL trees we looked at, but you don't need to reinvent a whole different approach. You might also find existing packages you might reuse in languages like Java for some of those data structures. However if you find a "line segment intersection" algorithm implemented somewhere you should not use that.
The algorithm from question 1.10, including a graphical demo component.
The algorithm from question 2.13.
The algorithm from question 2.14.
The triangulation algorithm for non-monotone polygons from chapter three.
(Not the full Art Gallery problem, just the making-monotone and triangulation).
The algorithm from question 3.10, including a graphical demo component.
The build and search algorithms for a 3-dimensional kD tree.
The build and query algorithms for a 3-dimensional range tree.
The randomized incremental algorithm of section 6.2.
The algorithm from question 6.9, including a performance comparison with your project 1.
The algorithms for constructing and using the data structure from question 6.16.
The algorithms for VoronoiDiagram in section 7.2, bonus for including a (in-house) graphical demo.
The algorithm for question 7.11.
An animated kD-tree showing construction, insertion and deletion of points.
Bonus points if you do and show rebalancing after operations.
Possibly a project of your own design, provided you meet with me to get it approved.

[ Back to CS661 Homepage ]