Algorithms seminar: Mattias Andersson

Date: June 22, 2006 (Thursday) at 14:15 to 15:00

Restricted Mesh Simplification using Edge Contractions

Joint work with Joachim Gudmundsson and Christos Levcopoulos.

Abstract: We consider the problem of simplifying a triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made onto one of its adjacent vertices. In order to maintain a high number of contractible edges under this restriction, a small modification of the mesh around the edge to be contracted is allowed. Such a contraction is denoted a 2-step contraction. Further, given m “important” points or edges it is shown that a simplification hierarchy of size O(n) and depth O(log (n/m)) may be constructed in O(n) time. Further, for many edges not even 2-step contractions may be enough, and thus, the concept is
generalized to k-step contractions.

Last modified Dec 9, 2011 12:59 pm