Assigned Projects for 2023-2024 Spring Semestr

Undergraduate Students:

All undergraduate students will do the same project.

Implementation of two-dimensional (2D) Convex Hull construction algorithms and comparing their performances (2 Students)

You will implement and compare the following Convex Hull algorithms to calculate and visualize the Convex Hull of a set of 2D points:

• Graham's Scan Algorithm.
• Jarvis March Algorithm.
• Quick Hull Algorithm.
• Merge Hull Algorithm.

Your program should generate the desired number of 2D points using the following distributions:

• Gaussian Distribution.
• Uniform Distribution.

We should be able to move and zoom in/out the 2D display of the points and the corresponding Convex Hull. We should be able to add new points manually by clicking on a specific position in the 2D space, which should cause the currently selected Convex Hull Algorithm to recalculate the modified Convex Hull. You should include an option to visualize the algorithms step-by-step; for example, we should see the partial Convex Hull being updated in an animated manner while the algorithm runs. You may check the Wikipedia entries of the algorithms for sample animations to get inspiration.

You will compare the performance of the three approaches using a reasonable number of test cases, e.g., starting with 1,000 and going up to 10,000,000 for constructing the Convex Hull from scratch. Also, compare the Convex Hull construction times in a dynamic setting; for example, start with an existing Convex Hull, add one new point to the space, and compare the performance of recalculating the Convex Hull with different approaches. In this case, the previously existing points will keep their order, and various algorithms will benefit from this configuration. In your report, you will also compare the performance of adding different numbers of points to an existing Convex Hull. For example, suppose the Convex Hull of 1,000 points is already calculated; how much time does each algorithm take to recalculate the new Convex Hull when we add 1, 10, 100, and 1,000 points?

Implementation of Two-dimensional (2D) Convex Hull Construction Algorithms and Comparing Their Performances

Yağız Alkılıç

Project Description

Implementation of Two-dimensional (2D) Convex Hull Construction Algorithms and Comparing Their Performances

Erkin Aydın

Project Description

Implementation of Two-dimensional (2D) Convex Hull Construction Algorithms and Comparing Their Performances

Bilgehan Yılmaz Sandıkçı

Project Description

Implementation of Two-dimensional (2D) Convex Hull Construction Algorithms and Comparing Their Performances (2 Students)

Mehmet Kağan İlbak and Recep Uysal

Project Description

Implementation of Two-dimensional (2D) Convex Hull Construction Algorithms and Comparing Their Performances (2 Students)

Tuna Okçu and Şeymanur Kılıç

Project Description

Implementation of Two-dimensional (2D) Convex Hull Construction Algorithms and Comparing Their Performances (2 Students)

Berkan Sivrikaya and Zeynep Derin Dedeler

Project Description

Implementation of Two-dimensional (2D) Convex Hull Construction Algorithms and Comparing Their Performances (2 Students)

Mehmet Feyyaz Küçük and Deniz Çelik

Project Description

Graduate Students:

PCB Plane Capacitance Calculator via Polygon Intersection

Oğuz Salar

Project Description

Enhancing Lloyd's Algorithm with Dual Voronoi Diagram Construction Approaches

Yusuf Ziya Özgül and Akmuhammet Ashyralyev

Project Description

Performance Comparison of 2D Delaunay Triangulation and 2D Voronoi Diagram on FPGA

Noor Muhammad

Project Description

Content-based Image Retrieval Using Deep Learning Based on Geometric Features

Fatih Yavuz

Project Description

Point Location Search Under Changing Environment

Mahmut Kemal Ercan

Project Description

Implementing Weighted Voronoi Stippling

Ömer Kaan Gürbüz

Project Description

2D Delaunay Triangulation Implementation on CUDA

Ekin Berk Ekinci

Project Description

Project Requirements

• You should give a project proposal until February 25th, 2024, 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 24th, 2024, 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 3 May-17 May 2024, depending on the number of groups.
  
  
• Each project group must submit a Final Project Report and a zipfile containing three directories (Due: May 17th, 2024, Friday, 23.59). 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