For those who really love solving problems, I've put together (in no particular order) some of the problems I enjoyed working on, in my Computational Geometry course. (Courtesy: Professor David Mount )
1. You are given a set of n vertical line segments in the plane. Present an O(n) efficient algorithm to determine whether there exists a line that intersects all of these segments.
2. Given a convex polygon P and a point w that is external to P, we say that a point q on the boundary of P is visible to w if the open line segment wq does not intersect P. Let P denote an n-sided convex polygon enclosed within a closed circular disk C. Present an O(n) time algorithm that, given P and C, determines whether there exist two points w1 and w2 lying within C but outside of P, such that every point on the boundary of P is visible to either w1 or w2 (or both).
3. You are given two sets, red points, R, and blue points, B, both having the same number of elements, n. Let p be any point in the plane (not in R or B). Prove that there exists a line l passing through p, such that the number of points of R that lie above l is equal to the number of points of B that lie above l. (This number need not be n/2.) Give an O(nlog n) algorithm that outputs such a line.
4. You are given a collection of vertical line segments in the first quadrant of the x, y plane. Each line segment has one endpoint on the x-axis and the other endpoint has a positive y-coordinate. Imagine that from the top of each segment a horizontal bullet is shot to the left. The problem is to determine the index of the segment that is first hit by each of these bullet paths. If no segment is hit, return the index 0. The input is a sequence of top endpoints of each segment pi = (xi, yi), for 1 <= i <= n, which are sorted in increasing order by x-coordinate. The output is the sequence of indices, one for each segment. Present an O(n) time algorithm to solve this problem.
5. In computer graphics, triangulations are used to represent surfaces. Graphics libraries like OpenGL support a special type of triangulation called a strip, which is defined as follows. For n >= 3, given a sequence of vertices V = <v1, v2, . . . , vn>, the strip of V consists of the n - 2 triangles <vi, vi+1, vi+2>, for 1 <= i <= n - 2. Assume that you are given an n-sided, x-monotone, simple polygon P as a sequence of vertices in counterclockwise order. Present an algorithm that determines whether P can be triangulated as a strip of the above form, such that its leftmost vertex is v1, and its rightmost vertex is vn.
6. Sometimes rather than computing a path that has minimum length, it is desirable to compute a polygonal path with the minimum number of segments. Consider the following situation. We are given an x-monotone n-sided polygon P. The lower chain is a convex chain. The upper chain is an arbitrary x-monotone polygon. Let s and t be the leftmost and rightmost vertices of P. The objective is to find a polygonal chain from s to t that lies within P that consists of the fewest number segments.
7. Given a set P of n points in the plane, the objective of this problem is to design an algorithm that determines the pair of concentric circles C1 and C2 such that every point of P lies between these circles, and the area of the region between these two circles is as small as possible.
Define FarP (pi) to be the set of all points in the plane that are strictly farther from pi than to any other site of P. As we did with Voronoi diagrams, we define the farthest-point Voronoi diagram to be the union of the boundaries of FarP (pi) for all points in P. Let NVD(P) denote the nearest-point Voronoi diagram of P and let FVD(P) denote the farthest-point Voronoi diagram of P.
Consider the subdivision S formed by overlaying NVD(P) and FVD(P). The vertices of S consist of the union of the vertices of the two Voronoi diagrams together with the points at which two edges, one from each diagram, intersect each other. give an O(k + n log n) algorithm for solving this problem, where k is the number of vertices of S.
(Hint:
Prove that the common center of the optimum concentric circles cannot lie in the interior of a face of S.
Prove that the common center of the optimum concentric circles cannot lie in the interior of an edge of S.
)
8. Given an n-vertex simple polygon P and an edge e of P, show how to construct a data structure to answer the following query in O(log n) time and O(n) space: Given a ray r whose origin lies on e and which is directed into the interior of P, find the first edge of P that this ray hits.