and then select one of the two options for the second part.
Part I --- Exercises
(Please do not consult outside sources, except your notes and text...)
1. Prove that the intersection of two convex sets is convex. Must the union of two convex sets be convex?
2. A region in the plane is called star-shaped if there is some point P in the set which can see all other points in the region.
a. Prove that every convex set is star-shaped
b. Must the intersection of two star-shaped sets be star-shaped?
3. The kernel of a star-shaped set is the set of points in that set which can see all other points in the set. For example, the star-shaped set to the right has the kernel indicated by a lighter shade of blue. Any point in this light blue set can see every point in the polygon. Prove that the kernel of any star-shaped set must be convex.
4. Sketch the Voronoi diagram of this set of points. For your convenience, the perpendicular bisectors of all pairs of points have all been drawn.
5. Now draw the Delaunay triangulation of that set. For each element of the Delaunay triangulation (vertex, edge, triangle) indicate to which element of your (appropriately labeled) Voronoi diagram from the previous problem it corresponds.
6. Draw the Voronoi poset for the Voronoi diagram you obtained in Problem 4. Please be sure to label the regions on the diagram and the poset, which I did not do in the example shown in the definition on the right.
7. There are n points in the plane in general position (no 3 on a line, no 4 on a circle) on which Alice has constructed a perfectly good Delaunay triangulation consisting of 2n - 10 triangles.
How many points are on the convex hull of this set?
Along comes Bob who adds a new point P to this set, which remains in general position. Now Alice has to rebuild her Delaunay triangulation.
Show that if /\ pqr is one of the triangles in Alice's
original triangulation, and its circumscribed circle
does not contain P, then that triangle will remain in
the new triangulation.
Show that if P is added to the interior of /\ pqr, then
each of the line segments Pp, Pq, and Pr will be
edges of the new Delaunay triangulation.
8. Build a Kirkpatrick hierarchy for this polygonal decomposition of a rectangular region. The answer should consist of a series of triangulations T0, T1, ..., Tk. T0 is a triangulation of the given figure, Tk is a rectangle with a single diagonal, and for i > 0, Ti is obtained from Ti-1 by the removal of an independent set, followed by a triangulation of the holes by the addition of diagonals only. Finally, a list of parents should be given for each triangle in T0, through Tk, where the parent of a triangle in T0 is the original polygon which contained it.
Part II --- Problems and Programs
Select one of the following tracks:
Theory
(Please do not consult outside sources, except your notes and text...)
9. We are given n points in the plane, all lying inside some large square, which we'll call target points. Show how to build a data structure in O(n log n) time so that given any query point inside that square, we can find the nearest target point in O(log n) time.
10. We defined the Delaunay triangulation as the straight line dual of the Voronoi diagram. In this dual, a Delaunay edge was drawn between any pair of points whose corresponding Voronoi regions shared a border. Prove that these Delaunay edges never cross. (Recall that this was an essential "observation" we made when concluding that the Delaunay triangulation was really a triangulation.)
Implementation
9. Write a program which, given an input file containing three points in the format:
10 20
21 19
-3 17
will output the center of the circle circumscribed through those points. Note that your program should handle the special case when the points are colinear, and there is no center.
10. Write a program to find a Delaunay triangulation of a set of points which may be asssumed to have integer coordinates, and no 4 on a circle. Your program may use the naive algorithm which simply finds all empty circles determined by three points and adds the corresponding triangle to the Delaunay triangulation. Here, the input will be points with labels, like this:
10 20 A
21 19 B
-3 17 C
12 -3 D
9 110 E
...
and the output should be the set of triangles, like this:
ABC
ADE
...
Some Definitions
ConvexA set is called convex if for every pair of points in the set, the line segment containing them is contained in the set.
Seeing
Two points in a planar set S are said to see each other if the line segment between them lies entirely inside the set S
Voronoi Poset
This is a way of showing the combinatorial structure of the Voronoi diagram. It consists of five rows of elements.
The
bottom row has a single element, labeled by the empty set '{}.'
The second row has an element for each Voronoi vertex, the third row
has an element for each Voronoi edge, the fourth row has an element for
each region in the Voronoi diagram, and the top row has a single
element labeled with the whole plane, R2.
Finally, an edge is drawn between elements of adjacent rows if their
corresponding objects are incident in the Voronoi diagram.
An example is shown below. Some Questions
Help with Delaunay!
You are not looking for empty triangles, but empty circles. To find if the circle determined by points A, B and C is empty, first find the center of the circle, and then test to see if any point other than A, B or C is closer to the center than those three points.
To find the center of the circle, find the intersection of the perpendicular bisectors of any two sides. To do that, you need to find the point of intersection of two lines. The best way to do that is to avoid the y=mx+b formulation for the equation of a line, and
rather use the ax+by=c formulation. Then finding the intersection is just solving two equations in two unknowns, which is easily done with Kramer's rule.