Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275758
Type: TESE
Title: Construção de separadores globalmente suaves para conjuntos de pontos no R2 e geração de base mínima
Title Alternative: Construction of globally smooth separators for sets of points in R2 and generation of minimum basis
Author: Malheiro, Ana Paula Resende
Advisor: Stolfi, Jorge, 1950-
Abstract: 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))

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))
Subject: Programação quadratica
Cônicas
Spline, Teoria do
Método dos elementos finitos
Language: Português
Editor: [s.n.]
Date Issue: 2011
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Malheiro_AnaPaulaResende_D.pdf11.12 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.