Projects for 2024-2025 Spring Semestr

Implementation of Parallel Delaunay Triangulation (2 Students)

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

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

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

Implementing Two Voronoi Diagram Computation Algorithms With Dynamic Manipulation and Comparing Their Performance (2 Students)

You are going to implement a program for calculating and visualizing the Voronoi Diagram of a set of points in 2D using the following two approaches:

• Randomized Incremental Algorithm that we will discuss in class.
• Fortune's Algorithm that uses a sweepline across the plane.

Note that as Delaunay Triangulation is the dual of the Voronoi Diagram, computation of the Voronoi Diagram may involve calculating its dual Delaunay Triangulation first.

Please see the following reference by Aurenhammer, F., Klein, R., for details on the Randomized Incremental and Plane Sweep (Fortune's) Algorithms:

"Voronoi Diagrams and Delaunay Triangulations", Aurenhammer, F., Klein, R., in the Handbook of Discrete and Computational Geometry, J.E. Goodman, J. O'Rourke, and C. D. Toth (editors), 3rd edition, CRC Press, Boca Raton, FL, 2017.

Voronoi Diagrams and Delaunay Triangulations

Your program should generate a set of random points in two dimensions using various distributions (Gaussian, uniform, etc.)as input and calculate and visualize the 2D Voronoi Diagram as graphical output. The program should have a good user interface to specify the parameters, such as the number of points and distribution parameters. Your program should support zooming in/out and moving the view while displaying the 2D Voronoi Diagram. You may assign different colors to each Voronoi Cell for better visualization.

After creating the 2D Voronoi Diagram, your program should also support dynamic manipulation of the Voronoi Cells. Specifically, we should be able to move the points to alter the Voronoi Cells. We should also be able to insert new points to create a new Voronoi Cell, affecting the neighboring cells. These two operations should operate on the existing Voronoi Diagram instead of building it from scratch.

You will visualize the steps of Fortune's Algorithm (we should see the visual result of the current Voronoi Diagram as the algorithm proceeds). You will also visualize the steps of the Randomized Incremental algorithm during the Delaunay triangulation construction. See the animated gif on the following page for an example step-by-step visualization of Fortune's algorithm:

Fortune's Algorithm

You will test your program for arbitrary point sets in 2D and report the performance of your implementation, comparing the two approaches. You must use a reasonable number of test cases, e.g., starting with 100 and up to 1,000,000.

Please also see the project description for the CS 274: Computational Geometry course at UC Berkeley by Prof. Dr. Jonathan Shewchuk at

Delaunay Triangulation Project

which also contains various test data sets that you can use.

Project Requirements

• You should give a project proposal until February 23rd, 2025, Friday (23.55) 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 March 21st, 2025, Friday (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 between 25 April-9 May 2025, depending on the number of groups.
  
  
• Each project group must submit a Final Project Report and a zipfile containing three directories (Due: May 13, 2025, Friday, 23.55). Final project report should be a superset of the the progress report and should extend it with implementation details, results of the project, etc. 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 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