This is an open-book exam. It is due at midnight the evening of Wednesday, December 15, 1999. You may submit your answers by email, under my office door, or through the U. S. Postal Service. If you choose the latter, your submission should be postmarked no later than December 15. Answers submitted after the deadline will not be accepted. You may consult papers and other references, but you may not receive assistance from other people (except me). You are welcome to ask me to clarify anything in the readings, the lectures, or this exam that you don't fully understand.

There are 28 points worth of questions below. Answer exactly 20 points worth. If you answer questions totalling more than 20 points, I will randomly select answers to ignore, bringing the total down to 20 points. If I ignore a question that you answered correctly and grade one that you got wrong, tough luck.

[1] Colliding fronts in paving (1 point). A simple way to check for colliding fronts in an advancing front triangular mesh generator is to maintain a constrained Delaunay triangulation of the void where vertices have not yet been generated. Why can't this idea be used in the paving algorithm without difficulty?

[2] Quadrilateral doublets (1 point). A doublet in a quadrilateral mesh is a pair of elements that share two adjacent sides. A doublet is considered topologically invalid, because at least one of the two quadrilateral elements must have an angle of 180^o or more in any planar embedding. Demonstrate that, by adding twist chords to the dual of the mesh, you can (topologically) eliminate all doublets from a mesh.

[3] Rivara refinement (1 point). Is the second Rivara refinement algorithm discussed by Bern and Plassmann guaranteed to terminate if applied to refining the 9-simplices of a 9-dimensional simplicial mesh? Explain your answer.

[4] Paving and smoothing (1 point). When smoothing is applied after mesh generation, it affects only the geometry, and not the topology, of the mesh. However, the paving algorithm uses smoothing during meshing, and not just as a postprocess. Does smoothing affect the paving algorithm's choice of where to place the next element? Explain your answer.

[5] Constrained Delaunay tetrahedra (2 points). Let X be a three-dimensional PLC, and let t be a tetrahedron whose vertices are in X. Suppose that no vertex of X lies in t except the four vertices of t, and no segment of X lies in the interior of t. Suppose that each of the four faces of t is either constrained Delaunay or is contained in a constraining facet of X. Prove that t is constrained Delaunay.

[6] Element-nested quadrilateral mesh refinement (2 points). The following statement is true for any triangular mesh M: ``Given any element e in M, it is possible to refine e while maintaining element-nesting by subdividing no more than c elements of M, where c is a constant independent of the mesh.'' (We can accomplish this by bisecting e and a neighbor sharing a common edge.)

Is the same statement true of any quadrilateral mesh M? Explain your answer.

[7] Subfacet splitting in Delaunay refinement (2 points). The three-dimensional Delaunay refinement algorithm discussed in the lecture notes generates elements whose circumradius-to-shortest edge ratios are no greater than two. To achieve this bound, the algorithm requires that encroached subfacets not be split in an arbitrary order. Instead, a subfacet may be split only if the orthogonal projection of an encroaching vertex lies in the subfacet. If encroached subfacets are split in an arbitrary order, what is the best bound on circumradius-to-shortest edge ratio that can (without extraordinary efforts) be proven using the same proof techniques employed in the lecture notes? Explain your answer.

[8] Minimum weight quadrilateralizations (2 points). Suggest how Step 5(a) of Montague and Dickerson's LMT-skeleton algorithm can be modified to help identify edges of the minimum weight quadrilateralization of a point set (whose convex hull has an even number of edges).

[9] Topological minimum weight triangulations (2 points). Given a weighted graph G whose nodes have not been assigned coordinates, consider the problem of finding a subgraph T of G whose total weight is minimum, under the constraint that T is the set of edges in some topological triangulation of the sphere, where the triangulation's vertices are the nodes of G.

Let's modify Dickerson and Montague's algorithm so that it attempts to eliminate some edges that are not in the topological minimum weight triangulation (TMWT). Topologically, there is no such thing as an ``empty edge'' or an ``empty triangle,'' so every edge of G is initially in candEdges, and every triangle whose edges are in G is initially in candTris. There is no convex hull, so we skip Step 4 of Dickerson and Montague's LMT-skeleton algorithm.

A certificate of the edge e = (u, v) is a pair of triangles uvw, uvx in candTris such that e is locally minimal with respect to uvw and uvx: that is, either (w, x) is not in G or the weight of (w, x) is greater than the weight of e. (Note that (u, v) and (w, x) are the diagonals of the quadrilateral uwvx.)

For each edge e in candEdges, if e has no certificate, then remove e from candEdges, and remove any triangle that has e for an edge from candTris. Perform several passes through candEdges, stopping only after no edge is eliminated during an entire pass.

If a TMWT T of G exists, we would like to say that every edge of T is in candEdges. Unfortunately, the algorithm is flawed: it may mistakenly eliminate edges of T from candEdges. What is the flaw? Why doesn't Dickerson and Montague's algorithm for geometric MWTs have this flaw?

[10] Hierarchical point location in Delaunay triangulations (2 points). Devillers describes a point location method that uses a node-nested sequence of Delaunay triangulations. Suppose the finest triangulation has n nodes and thus O(n) triangles. Say that the overhead of Devillers' method is the amount of additional memory--above and beyond the storage space used to hold the finest triangulation--allocated for point location data structures. Devillers' point location method has O(n) expected overhead, and O(log n) expected running time for one point location operation.

How can Devillers' method be modified so that its overhead is o(n) (that is, asymptotically less than linear space), but its running time is still O(log n)? (Hint: change the sizes of the triangulations used for point location.)

[11] Good-quality surface simplification I (2 points). Surface simplification algorithms (Hoppe; Garland and Heckbert) aren't normally concerned with the skinniness of the triangles they produce. But if one wants to simplify a scanned model in preparation for tetrahedralizing it, one may wish to avoid surface triangles with excessively small or large angles.

How can spacing function based coarsening be integrated with surface simplification so that the simplified mesh is likely to have good-quality triangles? (Hint: don't compute a maximal independent set.)

[12] Good-quality surface simplification II (2 points). Another way we might simplify surfaces without creating skinny triangles is smoothing.

• (a) Suppose that each time an edge is contracted, the resulting vertex is placed by optimization-based smoothing, with the goal of maximizing the minimum sine of the angles of the triangles incident on the vertex. Why is this a bad idea?
• (b) Why is the final position of the smoothed vertex sensitive to the position it initially had before the optimization algorithm was applied?

[14] Another view of quadric error metrics (2 points).

• (a) Explain how Garland and Heckbert's quadric error metrics can be used to identify the position of a vertex v that minimizes the sum of square distances to the vertices in v's preimage.
• (b) This use of quadrics can be combined with Heckbert and Garland's use, so that the location of a vertex v depends on a weighted average of the sum of square distances to planes associated with v's preimage, and the sum of square distances to vertices in v's preimage. What problem associated with Garland and Heckbert's method is solved this way? (Hint: Think of a perfectly flat triangulated surface.)

[16] Maximizing the area ratio (2 points). Let the area ratio of a triangulation be equal to the area of its largest triangle divided by the area of its smallest triangle. Given a simple polygon P, describe a cubic-time algorithm that finds a triangulation of P whose area ratio is at least as great as the area ratio of any other triangulation of P.