BCA608 2020F

Assignment 1 - due 27/11/2020

Triangulation by graph coloring

In this project you will create a software that will provide the following requirements. You can implement your software in any language/framework/engine you want. However, you must make sure that it can be eaily transferred to another computer (such as mine), and it can be demonstrated on demand.

Task

You are to create a program where the user can draw a polygon with the help of the mouse. Every time the user clicks on the screen, a new vertex is created and connected to the existing polygonal chain. When the user clicks Enter (or any other input event you want), the chain is closed and the polygon is constructed. You can assume that the user will never create a non-simple polygon. Then, your program will do the following:

1. It will find and store all diagonals of the polygon in a list.
2. It creates a diagonal graph where
   1. for each diagonal of the polygon, there is a corresponding node in the graph
   2. for every pair of intersecting diagonals, there is an edge between the corresponding graph nodes.
3. The program, then, randomly 2-colors the diagonal graph as follows:
   1. Randomly choose an uncolored node, u
   2. Color u as white
   3. Color all neighbors of u as black
   4. Repeat until all nodes are colored
4. Now consider the white nodes only and show that the corresponding diagonals result in a triangulation of the polygon
5. Analyze the complexity of your implementation

Submission

In this assignment, you will submit a report explaining your efforts and responses to the above requirements. You will also make a demonstration of your working program and deliver all code in executable form. You can submit your report and deliverables to burkaygenc@gmail.com.

Deadline

This submission is due 27/11/2020. There won't be any extensions as you are given plenty of time to complete the assignment. Do not start on the last day or you will fail to finish the tasks.