Mehmet Baris Caglar and Onur Aciicmez

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.

Presentation Date: May 2nd, 2001

M. Feyza Cosar

Implementation of Dynamic Convex Hull Algorithm in 2-dimensions.

Presentation Date: May 4th, 2001

Tolga Abaci and Ozgur Dogan Sahin

Implementation of Dynamic Convex Hull Algorithm in 3-dimensions.

Presentation Date: May 4th, 2001

Aziz Gulbeden ve Fehmi Kaya

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.

Presentation Date: May 9th, 2001

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.

Özer Aydemir and Gürcan Gülesir

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

Presentation Date: May 11st, 2001

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.

Ali Bugdayci and Ozgur Mersin

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.

Presentation Date: May 11st, 2001

Erdinç Basci and Mustafa Sakalsiz

Writing a program to find the closest and the farthest point for each point in 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.

Presentation Date: May 16th, 2001

Suha Onay, Burak Erturk and Serkan Sava

Implementation of some computational geometry algorithms in parallel.

Presentation Date: May 18th, 2001

? 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 ...