Project Topics for 2011-2012 Spring Semestr
- 2 students
-
Implementation of Path Planning Algorithms for Crowd Simulation.
The project should implement at least two different techniques for global
path planning and also address the issues related to local path planning.
The implementation should have good user interface and interactive
control mechanishms (realistic 3D output). You should also compare the performances
of the techniques qualitatively and quantitatively.
- 2 students
-
Implementation of Spatial Subdivision Algorithms for Particle Simulations.
The project should consider efficient update of dynamic spatial data structures for moving
point sets. The implementation should have good user interface and interactive
control mechanishms (realistic 3D output). You should also compare the performances
of the implemented techniques qualitatively and quantitatively.
- 2 students
-
Implementation of Dynamic Convex Hull Algorithm in 3-dimensions.
The implementation should have good user interface and interactive
control mechanishms (intuitive 3D input and realistic 3D output).
- 2 students
-
Implementation of a program finding the intersection, union, and
difference of two polygons in 2D. The polygons are not necessarily convex;
they may be concave. The program should have a good user interface
to enter the input points and to see the results.
- 2 students
- Implementation of the Orthogonal Range Searching.
You should use the kd-tree data structure for your implementation
as discussed in Preparata & Shamos textbook. The program should
take the input from the user by the help of mouse and/or randomly
and the output should be displayed appropriately (with different colors)
together with the input. Also, take the query range with the help of a mouse.
The implementation should also interactively show the kd-tree construction
over the input set.
- 2 students
-
Design and Implementation of 3D Voronoi Diagram for a set of points
in 3D. The program will be tested by using some random data and finding
the nearest neighbors of points using the 3D Voronoi Diagram. You should be
able to display the 3D output graphically.
- 2 students
-
Delaunay Tetrahedralization of 3D Volume Data for Direct Volume
Visualization. The program should be tested with an already existing
direct volume visualizer.
- 2 students
- Implementation of some computational geometry
algorithms in parallel. (Parallel Algorithms for Triangulating Point Sets,
Parallel Delaunay Triangulation, Parallel Convex Hull Algorithms,
Parallel Line Segment Intersection Algorithm, Parallel Voronoi Diagram,
Parallel Point Location). You can use PC-clusters.
- 2 students
- 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 students
- Implementation of a program to find the closest point
for each of the points in a set of points. The program will
use the sweeping technique and will show the running of the
algorithm step-by-step interactively.
-
- 2 students
-
Delaunay Triangulation on Multicore Architectures.
Recent works on Delaunay Triangulation methods
exploit parallelism via partitioning the points considering only
spatial locations. You should try to find better a model/method that
provides load balance and benefits from intrinsic properties of
multicore architectures.
References:
- Michael L. Scott, Michael F. Spear, Luke Dalessandro, and Virendra
J. Marathe, Delaunay Triangulation with Transactions and Barriers,
IEEE Intl. Symp. on Workload Characterization.
- Andrey N. Chernikov and Nikos P. Chrisochoides, Three-Dimensional
Delaunay Refinement for Multi-Core Processors, ICS'08.
-
- ? students
- Any other meaningfull project that you may come up with.
Project Requirements
-
You should give a project proposal until March 3rd, 2012, Thursday stating
the name of the project, a short project description of 2-3 paragraphs,
and name of the students that will do the project.
-
You will also give me a progress report (approximately 10 pages) until
Thursday, April 7th, 2012, 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 12th, 2011, Thursday.
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.
- Each project group must submit a CD containing three directories
(May 12, 2012, Thursday) just before the final exam. Please add new slides
to your presentation for the things that you explained on the board and
correct the typographical errors that we indicate during the presentations.
(The CD must be clearly labeled on the CD itself and must be put in a CD envelope
(which also have a label indicating group members, the name of the project, etc.):
- Documentation:
- Progress Report,
- Final Report
- Implementation
- Source Codes,
- Executables,
- README.TXT explaining how to install and run your program, user interface (how to use the buttons, mouse, etc.)
required libraries, databases, etc.
- Presentation
Ugur Gudukbay
Wed Jan 27 14:00:30 EET 2012