CSCI5010 Project Page
This is an individual project (i.e., you should not work with any other students). You need to implement an algorithm we discussed in the class. The implementation can be in either C++ or Java; other programming languages require an approval from the instructor.
Your implementation needs to be "from scratch with the exception of the binary search tree (BST)". This means that, you are allowed to deploy an existing implementation of the BST; but other than that, you can only use functions from a standard library, e.g.:
Use of any other functions is not permitted unless prior approval has been obtained from the instructor. All source codes are subject to plagiarism scrutiny (using some of the softwares listed here). All kinds of dishonesty will incur severe disciplinary penalty.
The deadline of the project is 12 May (i.e., 1 month from the day the project is released).
Data Formats
Your program needs to take the input from one or two files, and may need to output a set to a file. Both the input and output files must conform to the formats stipulated below.
A set of 2D points
The first line should contain a single integer n, which is the total number of points. Then, every subsequent line should specify a point (x, y) as follows:
x y
Note that the two coordinates are separated by a space. Each coordinate may be a real value. The file has n + 1 lines in total.
A set of 2D line segments
The first line should contain a single integer n, which is the total number of segments. Then, every subsequent line should specify a line segment connecting points (x1, y1) and (x2, y2) as follows:
x1 x2 y1 y2
Each coordinate may be a real value. The file has n + 1 lines in total.
A polygon
The first line should contain a single integer n, which is the total number of vertices in the polygon. Then, every subsequent line should specify a vertex point (x, y) as follows:
x y
The points are given in the clockwise order. Each coordinate may be a real value. The file has n + 1 lines in total.
A set of d-dimensional halfplanes
The first line should be
n d
where n is the total number of halfplanes, and d is the dimensionality. Then, every subsequent line should specify a halfplane in the set as follows:
c_1 c_2 ... c_{d+1}
which represents the plane that contains all d-dimensional points (x_1, x_2, ..., x_d) satisfying the inequality
c_1 * x_1 + c_2 * x_2 + ... + c_d * x_d >= c_{d+1}
The coefficients c_1, c_2, ..., c_{d+1} may be real values. The file has n + 1 lines in total.
Project List
You may choose to work on any of the following projects. The highest possible full mark is 25. However, these projects do not have the same difficulty; hence, they have different full marks as indicated below. Some projects have full marks less than 25.
You should attempt only one project (e.g., if you attempted both the convex hull and skyline projects, you receive a mark up to 15).
Grading
All the projects will be graded by the TA (whose contact information can be found on the course homepage). You must schedule an appointment with the TA to demonstrate your project by the deadline (12 May). Your grade will depend on how well your program satisfies the requirements listed for each project below. Multiple attempts are allowed until the deadline (e.g., if your program fails in your first appointment, you may schedule another appointment with the TA).
Please make sure you email a copy of your source code to the instructor and the TA. You are also strongly advised to prepare a visualization of your output whenever possible. A tool useful for this purpose is gnuPlot. Having the visualization ready will make it significantly easier when you demonstrate your submission to the TA.
Project 1: Convex Hull
Goal
Implement the Graham's algorithm in "Topic 1".
Input and Output
Input: A set of 2D points.
Output: A file containing the polygon that represents the border of the convex hull.
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's running time is no faster than O(n log n). You need to generate the datasets yourself. The largest dataset should have 1 million points.
- The TA may also use some other datasets (which you do not know in advance) to test your running time.
- Your program should return the correct output in all cases.
Project 2: Output-Sensitive Skyline
Goal
Implement the skyline algorithm in "Topic 2" that runs in O(n log k) time.
Input and Output
Input: A set of 2D points.
Output: A file containing the set of skyline points.
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's running time is no faster than O(n log k). You need to generate the datasets yourself. The largest dataset should have 1 million points.
- The TA may also use some other datasets (which you do not know in advance) to test your running time.
- Your program should return the correct output in all cases.
Project 3: Orthogonal Segment Intersection
Goal
Implement the planesweep algorithm in "Topic 3" that runs in O(n log n + m log m) time (where n is the number of horizontal segments, and m is the number of vertical segments).
Input and Output
Input: A set of horizontal segments, and a set of vertical segments.
Output: A file containing the set of intersection points.
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's running time is no faster than O(n log n + m log m). You need to generate the datasets yourself. In each dataset, there should be the same number of horizontal and vertical segments. The largest dataset should have 1 million segments in total.
- The TA may also use some other datasets (which you do not know in advance) to test your running time.
- Your program should return the correct output in all cases.
Project 4: Polygon Triangulation.
Goal
Implement the algorithm in "Topic 4" that runs in O(n log n) time.
Input and Output
Input: A polygon.
Output: A file containing the set of segments in the triangulation.
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's running time is no faster than O(n log n). You need to generate the datasets yourself. The largest dataset should be a polygon with 1 million vertices.
- The TA may also use some other datasets (which you do not know in advance) to test your running time.
- Your program should return the correct output in all cases.
Project 5: Linear Programming
Goal
Implement the algorithm in "Topic 5".
Input and Output
Input: A set of d-dimensional halfplanes (where the dimensionality d is less than 10).
Output: Display on the screen the point in the intersection of these halfplanes with the smallest coordinate on dimension 1. If the intersection is empty, output "no solution".
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's expected running time is no faster than O(n). You need to generate the datasets yourself. The largest dataset should contain 1 million halfspaces with dimensionality at least 4.
- The TA may also use some other datasets (which you do not know in advance) to test your running time.
- Your program should return the correct output in all cases.
Project 6: Minimum Enclosing Circle
Goal
Implement the algorithm in "Topic 6".
Input and Output
Input: A set of 2d points.
Output: Display on the screen the coordinates and radius of the circle found.
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's expected running time is no faster than O(n). You need to generate the datasets yourself. The largest dataset should contain 1 million points.
- The TA may also use some other datasets (which you do not know in advance) to test your
running time.
- Your program should return the correct output in all cases.
Project 7: Orthogonal Point Location
Goal
Implement the algorithm and structure in "Topic 8".
Input and Output
Input: A set of 2d horizontal segments.
Output: First, your program should produce a file containing all the segments in the trapezoidal map. Then, your program needs to wait for the user to input the x and y coordinates of a query point q. Then, your program must return instantly (i.e., with a negligible delay) the first segment hit by an upward ray emanating from q. After processing the query, your program must wait for the user to input another query, and continue in the same fashion.
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's expected time in building a trapezoid map is no faster than O(n). You need to generate the datasets yourself. The largest dataset should contain 1 million segments.
- As mentioned, your program must answer each point location query instantly.
- The TA may also use some other datasets (which you do not know in advance) to test your running time.
- Your program should return the correct output in all cases.
Project 8: Delaunay Triangulation
Goal
Implement the triangulation algorithm in "Topic 9".
Input and Output
Input: A set of 2d points.
Output: A file containing the segments in the delaunay triangulation.
Deliverables and Requirements
- Your program in an executable file and source code.
- Several test datasets that can be used to demonstrate that the growth of your program's expected time is no faster than O(n log n). You need to generate the datasets yourself. The largest dataset should contain 1 million points.
- The TA may also use some other datasets (which you do not know in advance) to test your running time.
- Your program should return the correct output in all cases.