Assigned Projects for 2025-2026 Spring Semestr

Undergraduate Students:

All undergraduate students will do the same project.

Implementing Two 3D Convex Hull Computation Algorithms and Comparing Their Performance (1 or 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.

Implementing Two 3D Convex Hull Computation Algorithms and Comparing Their Performance

Ali Deniz Sözer and Tuna Köksal

Project Description

Implementing Two 3D Convex Hull Computation Algorithms and Comparing Their Performance

Doruk Kolçak and Bartu Turan

Project Description

Implementing Two 3D Convex Hull Computation Algorithms and Comparing Their Performance

Emir Tomrukçu and Artun Berke Gül

Project Description

Implementing Two 3D Convex Hull Computation Algorithms and Comparing Their Performance

Amina Azizli

Project Description

Implementing Two 3D Convex Hull Computation Algorithms and Comparing Their Performance

Mehmet Akif Şahin

Project Description

Graduate Students:

Facial Expression Recognition via Geometric Delaunay Triangulation

Orkhan Karimli

Project Description

Decision Boundary Fragility Maps via Geometric Failure Analysis of Classifiers

Morteza Cham

Project Description

Recovering a Voronoi/Power Diagram from Distance-Transform Ridges

Melisa Tanrıkulu and Farzad Hallaji Azad

Project Description

Implementing Approximate Voronoi Cells for Solving CVP in Lattices with Low Dimensions

Barış Gülek

Project Description

Project Requirements

• You should give a project proposal until February 23rd, 2025, Sunday (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, and pseudo-codes to describe your approach.
  
  
• Presentations and demonstrations will be between 2-16 May 2025.
  
  
• Each project group must submit a Final Project Report and a zipfile containing three directories (Due: May 16, 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