Projects for 2025-2026 Spring Semester

Graduate Students:

I strongly encourage you to do a course project related to your research topic. We can arrange a meeting with you and your supervisor to determine a project topic that relates to both your research and computational geometry. Still, I provided a list of possible project topics below for those who cannot decide on a project related to their research topic.

Higher Order Voronoi Diagrams for k-Nearest Neighbor Queries (2 Students)

.... .....

Project Description

The Intersection of Axis Parallel Rectangular Prisms in 3D (2 Students)

... and ...

Project Description

Implementation of Parallel Delaunay Triangulation (2 Students)

You can choose any parallel programming platform to implement the Parallel Delaunay Triangulation and run experiments on the computational performance of your implementation, including speed-ups for different numbers of processors and various test data sets.

Please see the description of a divide-and-conquer algorithm by Guy Blelloch, Gary L. Miller, and Dafna Talmor. Implementation of Parallel Delaunay Triangulation

... and ...

Project Description

Robot Path Planning in Dynamic Environments Using Voronoi Diagrams (2 Students)

Please see the paper below for an implementation for mobile robots navigating in complex and dynamic environments by Ben Beklisi Kwame Ayawli, Xue Mei, Mouquan Shen, Albert Yaw Appiah, and Frimpong Kyeremeh. Mobile Robot Path Planning in Dynamic Environment Using Voronoi Diagram and Computation Geometry Technique

... and ...

Project Description

Selecting an Open Problem from the Open Problems Project (2 Students)

The Open Problems Project

edited by Erik D. Demaine, Joseph S. B. Mitchell, Joseph O'Rourke

Project Description

... and ...

Undergraduate Students:

All undergraduate students will do the same project.

Implementing Two 3D Convex Hull Computation Algorithms and Comparing Their Performance (2 Students)

You are going to implement a program for calculating and visualizing the three-dimensional (3D) Convex Hull of a set of points in 3D using the following two approaches:

• Gift Wrapping Algorithm by Chand and Kapoor.
• A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation by David A. Sinclair.

Please see the following references for these algorithms:

• David Sinclair, A 3D Sweep Hull Algorithm for Computing Convex Hulls and Delaunay Triangulation, Available at Newton Apple Wrapper (NAW) for Computing Convex Hulls and Delaunay Triangulation, 2016. This one includes C++ Code that you can use.
• Donald R. Chand and Sham S. Kapur (1970). An Algorithm for Convex Polytopes. Journal of ACM, Vol. 17, No. 1 (Jan. 1970), 78–86. Gift Wrapping Algorithm for computing the Convex Hull in Higher Dimensions, 1970.

Your program should generate a set of random points in 3D using various distributions as input, calculate and visualize the 3D Convex Hull as graphical output. The program should have a good user interface to specify parameters such as the number of points, zoom in/out, and translation while displaying/visualizing the 3D Convex Hull, both as a wireframe (hidden-surface removal) and as flat (polygon) shading, with the boundaries of the polygons drawn as well. You may also assign different colors to each boundary triangle for better visualization.

You will also implement visualizations of the steps for both algorithms (algorithm animation: we should see the visual result of the current 3D convex hull as the algorithm proceeds).

You will test your program on arbitrary 3D point sets and report the performance of your implementations, comparing the two approaches. You must use a reasonable number of test cases, e.g., starting with 1000 and up to 1,000,000 points.

Project Requirements

• You should give a project proposal by Feb 25, 2026, Wednesday (23.55) stating the name of the project, a short project description of 2-3 paragraphs, and the names of the students who will do the project.
  
  
• You will also give me a progress report (approximately 10 pages) until Mar 25, 2026, Wednesday (23.55), 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. Include illustrations, block diagrams, pseudo-codes to describe your approach.
  
  
• Presentations and demonstrations will be held between 22 April and 8 May 2026, depending on the number of groups.
  
  
• Each project group must submit a Final Project Report and a zipfile containing three directories (Due: May 8, 2026, Friday, 23.55). The final project report should be a superset of the progress report, adding implementation details, project results, etc. Please add new slides to your presentation covering the points you explained on the board, and correct the typographical errors we noted during the presentations. The zip file should be named as LastNameFirstName_LastNameFirstName_CS478_Project.zip or LastNameFirstName_LastNameFirstName_CS564_Project.zip. The directories must include
  
  
  1. Documentation:
     • Progress Report,
     • Final Report
  2. Implementation
     • Source Codes,
     • Executables,
     • README.TXT explaining how to install and run your program, user interface (input specification, how to use the buttons, mouse, etc.) required libraries, databases, etc.
  3. Presentation
     • Powerpoint Presentation