Questions and solutions : exam 1 of 2001
by Mike Soss


Question 1: You are given an image of 1's or 0's in a hexagonal array (black and white hexagonal pixels). Each set is connected. Invent an algorithm for contour tracing a connected pattern on this hexagonal grid. Your algorithm should be as simple as possible. Prove its correctness.
Question 2: (a) Describe the polygonal approximation algorithm of Melkman and O'Rourke. (b) Prove or disprove that it yields for a given fixed error tolerance the approximation with the minimum number of line segments.
Question 3: Let P be a simple polygon in the plane. Let S(m,f) be the skeletal pair of P, where m is the medial axis of P and f is the distance function. That is, f gives for every point x in m the distance (Euclidean) to the closest point on the boundary of P. Prove that given S(m,f), the original polygon P can be completely reconstructed. Your proof should be as formal, precise and detailed as you can make it.
Problem 1: Contour tracing on the hexagonal grid (3 points)

Note that there are no adjacent pixels which share only a vertex. Every pair of adjacent pixels shares an edge; thus a connected figure implies a simple boundary, similar to 4-connectedness on the square lattice. You can do this question in two easy ways based on algorithms you've seen in class.
  1. Modify Moore's algorithm
  2. Modify Square Tracing algorithm

Problem 2: Melkman & O'Rourke algorithm (4 pts)

It pains me that I can't give you any points if you wrote about a different algorithm. But if student A says, "I don't remember it at all," and student B writes a detailed analysis of a different algorithm, it wouldn't be fair to give student B more credit than student A.
Part a (2 pts)

The algorithm is described in your class handouts; I'm not going to retype it here. I was looking for the following facts, or equivalents. Part b (2 pts)

We have inputted all valid edges into the graph. Any edge which is not in the graph violates the tolerance. Therefore every edge of the shortest possible approximation is inside the graph. Taking the shortest path from start to finish finds a path with no more edges than this optimal approximation.


Problem 3: Medial Axis

The conjecture is true.

Many of you proved that each polygon has only one medial axis. It is obvious, by a deterministic algorithm, that each polygon has exactly one medial axis. You need to prove that each skeletal pair has exactly one polygon.

The easiest method is by taking the boundary of a union of circles. For each point m on the medial axis, we know the distance, f(m), to the point on the polygon P closest to m. For each point m of the medial axis, take the circle with radius f(m). I claim that the boundary union of all these circles is exactly the polygon P which created it. Since the union of these circles is unique, there is therefore a unique polygon P which created this skeletal pair.

I prove that the boundary of the union, U, is equal to the polygon, P. Each polygon makes a unique skeletal pair, and each skeletal pair gives rise to a unique polygon. We have a bijection, so either operation (polygon to pair, or pair to polygon) is invertible.