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?
Graduate Students:
I strongly encourage graduate students to do a course project related to your research topic.
We can arrange a meeting with you and your supervisor to determine such a project topic related to both
your research topic and computational geometry concepts. Still, I provide a list of possible roject topics
for graduate students below.
Implementation of Computational Geometry Algorithms on
Field Programmable Gate Arrays (FPGAs)
You can choose any parallel a computational geometry problem (e.g., (Convex Hulls, Voronoi Diagrams, Delaunay Triangulations)
and implement two algorithms for that problem on FPGAs and compare their computational performances. You should also make necessary arrangements to visualize
the computational geometry objects calculated using FPGAs on CPUs.
Implementation of Parallel Delaunay Triangulation (2 Students)
You can choose any parallel programming platforms, e.g., Graphics Processing Units (GPUs), and libraries, e.g., CUDA (Compute Unified Device Architecture), to implement the Parallel Delaunay Triangulation and make experiments for the computational performance of your implementation, such as the speed-ups
for different number of processors, for various test data.
Please see the description of a divide-and-conquer algorithm by Guy Blelloch, Gary L. Miller, Dafna Talmorat,
Implementation of Parallel Delaunay Triangulation
... and ...
Project Description
Higher Order Voronoi Diagrams for k-Nearest Neighbor Queries (2 Students)
.... and .....
The Intersection of Axis Parallel Rectangular Prisms in 3D (2 Students)
... 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, 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 ...
Higher Level Voronoi Diagrams for k-Nearest Neighbor Queries (2 Students)
.... .....
Project Description
... ...
... ...
Project Description
Project Requirements
-
You should give a project proposal until February 23th, 2024, 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 15th, 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
- Documentation:
- Progress Report,
- Final Report
- 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.
- Presentation
Ugur Gudukbay
January 19, Friday, 14:30:30 EET 2024