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.
- Modify Moore's algorithm
- In Moore's algorithm, we find the first black pixel. We then exit the way we entered, and go clockwise about this pixel until we hit one of its neighbours (or discover that it's an isolated pixel). When we enter a neighbour, we backtrack and look for its next clockwise neighbour, and so on. We stop when we enter the second pixel in the same way we entered it. Note that entering the first pixel in the same manner may never happen!
- The proof of correctness is identical to that of Moore's algorithm. We are tracing the contour in the clockwise direction.
- Modify Square Tracing algorithm
- The bug always turns a sharp right when outside the polygon,
and a sharp left when inside. Thus the bug hugs a vertex (adjacent to three hexagons) of the grid until it crosses the next edge of the boundary. At this point, because the figure and ground are connected,
the proof is identical to
that for the square-tracing version
.
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.
- It's an O(n^2 log n) time version of Iri & Imai's O(n^3) algorithm.
- The idea of entering all valid edges into a graph and then finding the shortest path from start to goal.
- Their geometrical idea of line segments piercing circles, or their wedge structure which allows the faster method.
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.
- U is contained in P.
- Each circle is centered inside the polygon, and its radius is equal to the shortest distance from the centre to the boundary of P. Therefore no circle can possibly extend beyond the boundary of P.
- P is contained in U. (This is the crucial part!)
- Select a point p on the boundary of P. Consider the region inside the polygon of all points whose
closest point on the boundary is p (the Voronoi cell of p, which may be a line segment).
This region contains a line segment normal to the boundary at p. Follow this line segment until I leave the region at some point m. Now I must be in the region of some other point, say q. Follow a line segment to q, which I know must be normal to the boundary at q. The vertex m between the two regions must be equidistant to p and q. Furthermore, p and q are the closest points on the boundary to m, and pm and qm are normal to the boundary of P. This is the definition of a medial axis point. Therefore m is on the medial axis, and f(m) is the distance mp = mq. Therefore p is in the circle centered at m with radius f(m), and is
union of the circles.
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.