2 Persons

Implementation of 3 convex hull algorithms (in 2 dimensions) and comparing their performances. The algorithms could be Graham Scan, Jarvis's March, Gift Wrapping, QuickHull. The program should have a good user interface.

1 Person

Implementation of Dynamic Convex Hull Algorithm in 2-dimensions.

2 Persons

Implementation of a program finding the Voronoi diagram for a set of points (in 2 dimensions) The program should have a good user interface to enter the input points and to see the results. The program will be used to determine the nearest-neighbor of a given point together with the nearest distance.

2 Persons

Implementation of data structures for efficient hit testing in graph editing where the nodes representated by rectangles are of arbitrary sizes and edges are represented by line segments. The bounds of the graph may change by the graph editing operations.

2 Persons

Implementing the Turning Angle Method for shape similarity with the capability of accepting data from an Object Extractor Tool.

Detailed Desciption: This project includes a computational geometry-based method, turning angle, where its source file for C is publicly available. The students will implement this project in Java to perform better with a Java GUI. Since the project will be used for shape similarity and pattern matching as part of a multimedia query interface, in order to accept data from the Object Extractor Tool, the students need to add methods related with not only computational geometry but also computer graphics. The extracted object from the tool is just a set of pixels on x-y space and eventually it has to be converted to a set of coordinates ordered in counterclockwise direction representing the object as a polygon. The number of sides for the polygon, N, can be an input from the user and the resultant polygon will be a set of N vertices or coordinates. This polygonalization requires a processing for the boundary pixels. The students may find the most appropriate method for this process.

2 Persons

Implementation of Delaunay Triangulation in 3-dimensions. The program should have a good user interface to enter the input points and to see the results.

2 Persons

Writing a program to find the closest two and the farthest two of a set of N points in 2-dimensions. The program should have a good user interface to enter the input points and to see the results.

2 Persons

Implementation of some computational geometry algorithms in parallel.

? Persons

Any other meaningfull project that you may come up with

Project Requirements

• You should give a project proposal until March 2st, 2001 stating the name of the project and name of the students that will do the project.
• You will also give me progress report (approximately 10 pages) until April 6th, 2001 about the progress of your project, covering a survey of the subject area, algorithms that you will use, data structures, and other implementation details, etc.
• Final project report and demonstrations will be due May 11th Friday. This deadline is sharp. Final project report should be a superset of the the progress report and should extend it with implementation details, results of the project, etc.
• At the end, I expect to students to port their projects to my SGI Octane Workstation (or PC if it is done for PC's).

• About this document ...