[pt] Um campo de linhas sobre uma superfície é um mapa suave que atribui uma linha tangente a todos, exceto a um número finito de pontos. Esses campos modelam um número de propriedades geométricas e físicas, tais como as direções de curvatura principais nas superfícies ou o fluxo de tensão na elasticidade. Para entender um campo de linha, é usual estudar o comportamento de suas órbitas, que podem apresentar diferentes padrões. Para este fim, consideramos uma abordagem topológica que consiste em utilizar os pontos críticos e separatrices para decompor o campo em regiões de comportamento homogêneo. Focamos em campos que possuem uma estrutura de Morse–Smale. Isso permite operações como o cancelamento de pontos críticos controlados diretamente na decomposição de campo, o que é essencial para a remoção de ruído (simplificação da topologia) em campos provenientes de simulações ou amostragem de problemas do mundo real. Baseado na decomposição de um campo vetorial de Morse–Smale e no cancelamento de pontos críticos, Robin Forman introduziu uma definição discreta para esses campos. O presente trabalho fornece uma definição puramente combinatória para campos de linhas, os campos de linhas discretos, que implicam as construções discretas de Forman para campos de vetores por meio de uma nova representação destes. Campos de linhas discretos admitem uma decomposição que gera uma ponte entre os campos de linhas discretos e suaves, garantindo dessa forma a consistência topológica da definição. Também estabelecemos uma conexão entre um campo de linha discreto e um campo vetorial discreto, desse modo as ferramentas de campos de vetores podem ser usadas em campos de linhas. O trabalho fornece ainda um cancelamento topologicamente consistente de seus elementos críticos para um campo de linha discreto. / [en] A line field on a surface is a smooth map that assigns a tangent line to all but a finite number of points. Such fields model a number of geometric and physical properties, e.g. the principal curvature directions on surfaces or the stress flux in elasticity. They can be seen as a generalization of vector fields. To understand a line field, it is common to study the behavior of its orbits, which can have many different patterns. To this end, we consider a topological approach: we use the critical points and separatrices to decompose the field in regions of similar behavior. We focus on fields that have a Morse–Smale structure. This allows operations like the cancellation of critical points controlled directly in the field decomposition, which is essential for noise removal (topology simplification) on fields coming from simulations or sampling of real-world problems. Based on the decomposition of a Morse–Smale vector field and on cancellation of critical points, Robin Forman introduced a discrete definition for Morse-Smale vector fields. This thesis provides a purely combinatorial definition of line fields, the discrete line fields, entailing Forman s discrete constructions for vector fields through a new representation of these. Discrete line fields admit a (Morse–Smale type of) decomposition that generates a bridge between discrete and smooth line fields, thus guaranteeing the topological consistency of the definition. We also use double branched coverings to suspend discrete line fields to discrete vector fields, so that vector field tools can be used for discrete line fields. Finally we provide, for a discrete line field, a topologically consistent (Morse-like) cancellation of critical elements. This allows a simplification of the discrete line field topology retaining only the most significant features.

[pt] A teoria de Morse relaciona a topologia de um espaço aos elementos críticos de uma função escalar definida nele. Isso vale tanto para a teoria clássica quanto para a versão discreta proposta por Forman em 1995. Essas teorias de Morse permitem caracterizar a topologia do espaço a partir de funções definidas nele, mas também permite estudar funções a partir de construções tipológicas derivadas dela, como por exemplo o complexo de Morse-Smale. Apesar da teoria de Morse discreta se aplicar para complexos celulares gerais de forma inteiramente combinatória, o que torna a teoria particularmente bem adaptada para o computador, as funções usadas na teoria não são amostragens de funções contínuas, mas casamentos especiais no grafo que codifica as adjacências no complexo celular, chamadas de casamentos de Morse. Quando usar essa teoria para estudar um espaço topológico, procura- se casamentos de Morse ótimos, i.e. com o menor número possível de elementos críticos, para obter uma informação topológica do complexo sem redundância. Na primeira parte desta tese, investiga-se a complexidade parametrizada de encontrar esses casamentos de Morse ótimos. Por um lado, prova-se que o problema ERASABILITY, um problema fortemente relacionado à encontrar casamentos de Morse ótimos, é W [P ]-completo. Por outro lado, um algoritmo é proposto para calcular casamentos de Morse ótimos em triangulações de 3-variedades, que é FPT no parâmetro do tree- width de seu grafo dual. Quando usar a teoria de Morse discreta para estudar uma função escalar definida no espaço, procura-se casamentos de Morse que capturam a informação geométrica dessa função. Na segunda parte é proposto uma construção de casamentos de Morse baseada em casamentos estáveis. As garantias teóricas sobre a relação desses casamentos com a geometria são elaboradas a partir de provas surpreendentemente simples que aproveitam da caracterização local do casamento estável. A construção e as suas garantias funcionam em qualquer dimensão. Finalmente, resultados mais fortes são obtidos quando a função for suave discreta, uma noção definida nesta tese. / [en] Morse theory relates the topology of a space to the critical elements of a scalar function defined on it. This applies in both the classical theory and a discrete version of it defined by Forman in 1995. Those Morse theories permit to characterize a topological space from functions defined on it, but also to study functions based on topological constructions it implies, such as the Morse-Smale complex. While discrete Morse theory applies on general cell complexes in an entirely combinatorial manner, which makes it suitable for computation, the functions it considers are not sampling of continuous functions, but special matchings in the graph encoding the cell complex adjacencies, called Morse matchings. When using this theory to study a topological space, one looks for optimal Morse matchings, i.e. one with the smallest number of critical elements, to get highly succinct topological information about the complex. The first part of this thesis investigates the parameterized complexity of finding such optimal Morse matching. On the one hand the Erasability problem, a closely related problem to finding optimal Morse matchings, is proven to be W[P]-complete. On the other hand, an algorithm is proposed for computing optimal Morse matchings on triangulations of 3-manifolds which is fixed parameter tractable in the tree-width of its dual graph. When using discrete Morse theory to study a scalar function defined on the space, one looks for a Morse matching that captures the geometric information of that function. The second part of this thesis introduces a construction of Morse matchings based on stable matchings. The theoretical guarantees about the relation of such matchings to the geometry are established through surprisingly simple proofs that benefits from the local characterization of the stable matching. The construction and its guarantees work in any dimension. Finally stronger results are obtained if the function is discrete smooth on the complex, a notion defined in this thesis.