1. Research open problems
Some of the open problems are
summarized in [1]. The research should include a programming part with
the goal to demonstrate the problem ...
2. Generate
random polygon
The task is to
generate a random polygon using different approaches: incremental,
divide-and-conquer, onion peeling, flipping edges, gift-wrapping/monotone
algorithms.
3. Find the convex hull of star-shaped
polygons
The task is to generate convex
hull of a star-shaped polygon. A star shaped polygon may be generated from the input set of points.
One possibility is to have two buttons: button “Star-Shaped Polygon” for
generating star-shaped polygons based on the input set of points, and button
“Convex Hull” for generating the convex hull based on the polygon. The
input points are entered using mouse clicks.
4. Compute number of possible triangulations
This is a combinatorial problem.
Given a polygon, determine how many triangulations are possible to generate. The input polygon is entered
using mouse clicks.
5. Compute number of possible polygons
This is a combinatorial problem.
Given a set of points, determine how many polygons are possible to generate. The input
set of points is entered
using mouse clicks.
6. Merge
polygons
The task is to
merge two polygons (inner and outer polygons). It is necessary to select a
pair of visible edges on the outer and inner polygons. Merge the polygons by
“opening” these edges and connecting the necessary end points using two
segments.
10. Construct
convex hull
The task is to implement
the following algorithms to determine and display the convex hull of a
set of points: Graham’s scan, Incremental algorithm, Gift wrapping, Divide-and-conquer. The input is a set of points, entered using mouse clicks.
11. Determine
point location
The problem is to detect whether
the point is in the polygon or not. The implementation should include building a data structure (Kirkpatrick’s)
for querying a point in O( log N ) time.
The input polygon is entered using mouse clicks. Once the polygon is closed,
consequent mouse clicks create points, which should be tested. Button “Reset” should
clear the polygon and the points.
12. Intersect two arbitrary polygons
The problem is to intersect two
polygons using plane-sweep algorithm.
13. Display triangulation dual
The task is to display a triangulation
and its dual. The input polygon is entered using mouse clicks.
Other problems are: Nearest neighbor path, Minimum spanning tree, Traveling salesperson problem,
Voronoi diagram (Divide-and-couquer, Incremental, Fortune's) and Delaunay
diagrams (Flipping diagonals, incremental).