Resumo: Esta tese tem duas partes relativamente independentes. A primeira estuda o problema de construir uma curva suave (C1) que separa dois conjuntos de pontos do plano. Especificamente, a curva é definida por uma equação implícita F(x, y) = 0 onde F é uma spline polinomial de grau 2 com continuidade adequada. O objetivo é determinar uma única cônica se possível, senão uma curva que minimiza uma função quadrática de "energia". O problema é reduzido a um problema de minimização quadrática com restrições, que é resolvido por uma biblioteca existente (CGAL). A segunda parte descreve um algoritmo geral para determinar uma base de elementos finitos em um espaço de splines arbitrário, definido por exemplo por restrições lineares homogêneas de continuidade ou contorno. Neste caso o problema é caracterizado como o problema de encontrar uma base de peso máximo em um matróide e, portanto, pode ser resolvido pelo algoritmo guloso de Edmonds. Esse algoritmo tem custo exponencial no número n de células da malha. Entretanto, esta tese mostra que para casos de interesse - onde existe uma base de elementos finitos com suporte de k células, no máximo - o algoritmo pode ser melhorado de modo a terminar em tempo O(n km3), onde m é a dimensão do espaço (que é geralmente O(n)) Ver menos

Abstract: This thesis has two relatively independent parts. The first part considers the problem of constructing a smooth (C1) curve separating two sets of points of the plane. Specifically, the curve is defined by an implicit equation F(x, y) = 0, where F is a polynomial spline of degree 2 with appropriate continuity. The goal is to determine a unique conic wherever possible, or a piecewise-defined curve that minimizes a quadratic "energy" function. The problem is reduced to a quadratic minimization problem with constraints, which is solved by an existing library (CGAL). The second part describes a general algorithm to determine a finite-element basis on an arbitrary space of splines; for example, a space defined by homogeneous linear boundary or continuity constraints. In this case the problem is defined as the problem of finding a maximum weight basis in a matroid, and therefore can be solved by the greedy algorithm of Edmonds. This algorithm has exponential cost in the number n of mesh cells. However, we show that for cases of interest - wherever there is a finite-element basis with maximum support of ? cells - the algorithm can be improved so as to finish in time O(n km3), where m is the dimension of the space (which is usually O(n)) Ver menos