M.Sc Student Steiner Aya Matability of Polygons Department of Applied Mathematics Professor Gill Barequet

Abstract

Interpolating a piecewise-linear triangulated surface between two parallel slices, each consisting of an arbitrary number of (possibly nested) polygons that define material and non material regions, has attracted a lot of attention in the literature in the past two decades. Practically all currently-known surface reconstruction from parallel slices methods take the existence of a mating of the polygons for granted. A related interesting question is, given two nonmatable polygons, whether or not one is able to add vertices on the boundary of the polygons so as to make them matable, and if so, how many such vertices suffice to guarantee a mating.

In this thesis we provide proof of the nonmatability of a simple pair of polygons. We also provide, for the first time, a family of nonmatable pairs of polygons, with unbounded complexity. We also give a few sufficient conditions for polygon matability. We show that when the addition of Steiner vertices on the boundary of the polygons is permitted, if one polygon is convex, then one Steiner point suffices to guarantee mating. (If the two polygons are convex, then no Steiner vertices are needed at all.)

We also present an efficient method for interpolating a piecewise-linear surface between two polygons that define "material" and "nonmaterial" regions. Our method is fully automatic and is guaranteed to produce non-self-intersecting surfaces in all cases regardless of their complexity and geometry. The method is based on computing the cells of the symmetric difference of the two polygons. Then, the straight skeletons of the selected cells guide the triangulation of each face of the above cells. Finally, the resulting triangles are lifted up in space to form an interpolating surface. We provide some experimental results on various complex examples to show the good and robust performance of our algorithm.