We propose in this thesis a way to study deformations of plane curves that take into consideration the geometry of the curves as well as their singularities. We deal in details with local phenomena that occur generically in two-parameter families of curves. We obtain information on the inflections and vertices appearing on the deformed curves. We also obtain the configurations of the evolutes of the curves and of their deformations, and apply our results to orthogonal projections of space curves. Finally, we consider the profile (outline, apparent contour) of a smooth surface in the Euclidian 3-space. This is the image of the singular set of an orthogonal projection of the surface. The profile is a plane curve and may have singularities. We study the changes in the geometry of the profile as the direction of projection changes locally in the unit sphere. / Propomos nesta tese um método para estudar deformações de curvas planas que leva em consideração a geometria delas, bem como as suas singularidades. Consideramos em detalhes os fenômenos locais que ocorrem genericamente em famílias de curvas com dois parâmetros. Obtemos informações sobre as inflexões e vértices que aparecem nas curvas deformadas. Obtemos também as configurações das evolutas das curvas e das suas deformações e aplicamos os nossos resultados nas projeções ortogonais de curvas espaciais. Finalmente, consideramos o perfil de uma superfície regular no espaço Euclidiano R3. O perfil é a imagem do conjunto singular de uma projeção ortogonal da superfície, esta é uma curva plana e pode ter singularidades. Estudamos as alterações na geometria do perfil quando a direção de projeção muda localmente na esfera unitária.

Let G be a simple graph on n vertices, and let S(G) be the class of all real-valued symmetric nxn matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The smallest rank achieved by a matrix in S(G) is called the minimum rank of G, denoted mr(G). The maximum nullity achieved by a matrix in S(G) is denoted M(G). For each graph G, there is an associated minimum rank class, MR(G) consisting of all matrices A in S(G) with rank A = mr(G). Although no restrictions are applied to the diagonal entries of matrices in S(G), sometimes diagonal entries corresponding to specific vertices of G must be zero for all matrices in MR(G). These vertices are known as nil vertices (see [6]). In this paper I discuss some basic results about nil vertices in general and nil vertices in cographs and prove that cographs with a nil vertex of a particular form contain two other nil vertices symmetric to the first. I discuss several open questions relating to these results and a counterexample. I prove that for all cographs G without an induced complete tripartite graph with independent sets all of size 3, the zero-forcing number Z(G), a graph theoretic parameter, is equal to M(G). In fact this result holds for a slightly larger class of cographs and in particular holds for all threshold graphs. Lastly, I prove that the maximum of the minimum ranks of all cographs on n vertices is the floor of 2n/3.

The project set out to construct a proof of concept for surface deformation in the Unity Engine using available assets and tools compatible with the Unity Engine, and via the proof of concept investigate which factors in a mesh deformation simulation that affects performance in terms of frames per second, memory usage and usability the most. This while looking into suitable data structures in the Unity Engine for handling expected data in a physics simulation of a surface deformation, such that of mining or scraping a cave wall. The project aims to answer these questions via testing and trail and error, performing tests while recording data which is plotted and discussed. To save time and start testing faster the usage of a premium assets called Digger Pro is used, allowing for quick set up of mesh manipulation inf both editor and play mode. Testing shows that one of the major factor for performance degradation is mesh resolu-tion, as it directly contributes to an increase in data points that needs to be kept track of and calculated. The Unity Engine and Digger PRO man-ages fairly well to stay above the targeted 30 frames per second limit even with medium level settings for meshes, all while maintaining acceptable memory usage levels. All this ties into the idea of an increased usage of digital twins in many different scenarios, and therefore the scientific community’s view on digital twins main challenges are summarized and discussed, hoping to shed further light on the current status of digital twin technology.

[pt] O objetivo deste trabalho é estudar uma certa classe de polígonos espaciais e provar teoremas a respeito do número mínimo de achatamentos que tais polígonos necessariamente possuem. Para tal, investigamos polígonos esféricos que não estão contidos em nenhum hemisfério fechado e deduzimos, entre vários resultados, que sob certas hipóteses tais polígonos esféricos possuem uma cota inferior não-trivial para o número de inflexões esféricas. / [en] The aim of this work is to study a certain class of spatial polygons and prove theorems on the minimal number of flattenings that such polygons must have. In order to do this, we investigate spherical polygons which are not contained in any closed hemisphere and deduce, among many results, that under certain hypotheses such spherical polygons have a nontrivial lower bound on the number of spherical inflections.

Baigiamajame magistro darbe nagrinėjama paprasto skylėto daugiakampio skaidymo į dalis, kurių viršūnių skaičius neviršyja nustatyto skaičiaus problema. Apibrėžiamas uždavinys ir jo svarba. Apžvelgiami egzistuojantys skaidymo algoritmai, padedantys išspręsti uždavinį, bei jų realizacijos. Pateikiamos trianguliacijos ir padalinimo į apytiksliai iškilius daugiakampius algoritmų modifikacijos, jų privalumai ir trūkumai. Įvertinamas šių modifikuotų algoritmų sudėtingumas. Eksperimentinėje dalyje pateikiami skaičiavimo eksperimentų rezultatai, jų analizė ir palyginimas su teoriniais algoritmų sudėtingumo įverčiais. Remiantis skaičiavimo eksperimentų rezultatais pateikiamos išvados ir siūlymai. / This study deals with decomposition of simple polygon with holes into components so that every piece does not exceed some defined number of vertices. We define the problem and its appliances. Existing studies and algorithms for polygon decomposition are covered. We propose modifications of polygon triangulation and approximate convex decomposition algorithms. Also the complexity analysis of both algorithms is made. In the experimental part of the work results of computing experiments are presented, analyzed and compared to the theoretical complexity bounds.

The imaginary part of the retarded self energy is of particular interest as it contains a lot of physical information about particle interactions. In higher order loop diagrams the calculation become extremely tedious and if we have to do the same at finite temperature, it includes an extra dimension to the difficulty. In such a condition we require to switch between bases and select the best basis for a particular diagram. We have shown in our calculation that in higher order loop diagrams, at finite temperature, the R/A basis is most convenient on summing over the internal vertices and very efficient on calculating some particular diagrams while the result is most easily interpretable in the Keldysh basis for most other complex diagrams. / February 2010

La morphologie mathématique est une théorie puissante pour l’analyse d’images 2 D. Elle se base sur la dilatation et l’érosion, qui correspondent à l’addition et la soustraction de Minkowski. Afin d’analyser des maillages 3D par morphologie mathématique, on doit disposer d’algorithmes performants et robustes pour le calcul exact de l’addition et de la soustraction pour ces maillages. Malheureusement, les travaux existants sont, soit approximés, soit non robustes ou limités par des contraintes. Aucun travail n’a traité la différence. Ces difficultés sont dues au fait qu’un maillage représente une surface linéaire par morceaux englobant un ensemble contenu et non dénombrable. Nous avons introduit la notion de sommets contributeurs et nous avons développé un algorithme efficace et robuste pour le calcul de la somme de polyèdres convexes. Nous l’avons par la suite adapté et proposé deux algorithmes performants pour la somme d’une paire de polyèdres non convexe/convexe, tout en gérant correctement les polyèdres complexes, les situations de non-variété ainsi que les changements topologiques. Nous avons également démontré la dualité des sommets contributeurs et nous l’avons exploité pour développer la première approche du calcul exact et efficace de la différence de polyèdres convexes. La dualité des sommets contributeurs ainsi que la robustesse et l’efficacité de nos approches motivent le développement d’une approche unifiée pour l’addition et la soustraction de polyèdres quelconques, ce qui permettra d’appliquer des traitements morphologiques à des maillages 3D. D’autres domaines tels que l’imagerie médicale, la robotique, la géométrie ou la chimie pourront en tirer profit / Mathematical morphology is a powerful theory for the analysis of 2D digital images. It is based on dilation and erosion, which correspond to Minkowski addition and subtraction. To be able to analyze 3D meshes using mathematical morphology, we must use efficient and robust algorithms for the exact computation of the addition and subtraction of meshes. Unfortunately, existing approaches are approximated, non-robust or limited by some constraints. No work has addressed the difference. These difficulties come from the the fact that a mesh represents a piecewise linear surface bounding a continuous and uncountable set. We introduced the concept of contributing vertices and developed an efficient and robust algorithm for the computation of the Minkowski sum of convex polyhedra. After that, we adapted and proposed two efficient algorithms for the computation of the Minkowski sum of a non-convex/convex pair of polyhedra, while properly handling complex polyhedra, non-manifold situations and topological changes. We also demonstrated the duality of the contributing vertices concept and exploited it to develop the first approach for the efficient and exact computation of the Minkowski difference of convex polyhedra. The duality of the contributing vertices concept as well as the robustness and efficiency of our approaches motivate the development of a unified approach for the Minkowski addition and subtraction of arbitrary polyhedral, which will permit the morphological analysis of 3D meshes. Other areas such as medical imaging, robotics, geometry or chemistry may benefit from our approaches

Malhas dinâmicas são comumente utilizadas em problemas de simulação sobre dominios cuja geometria varia com o tempo. Sempre que o domínio onde a malha está definida é alterado, as molas são acionadas movimentando os vértices para que estes se conformem com a nova descrição do domínio. Os tipos de molas mais utilizadas são: as longitudinais, as torcionais e as semi-torcionais. Nesta tese uma nova mola é proposta, a mola altura, que além de evitar sobreposição de elementos, é conceitualmente simples e fácel de ser implementada. Outra contribuição desse trabalho é o mecanismo de vértices ativos, que permite economia de processamento durante a resolução da malha dinâmica. Quando a fronteira do domínio sofre grandes alterações, o processo dinâmico pode não ter êxito na correção da malha. Para contornar esse problema, a fronteira deve ser alterada aos poucos. Uma nova estratégia para realizar grandes deformações em pequenos passos é introduzida nesta tese. Em algumas aplicações, o movimento da fronteira da malha pode comprometer células da própria fronteira. A correção da fronteira e um processo delicado, já que em muitos casos ele implica em alterar a descrição do domínio. Um novo método para efetuar a correção da fronteira é apresentado neste trabalho. Ele é baseado em malhas dinâmicas e utiliza um novo conceito de molas, as molas conservativas. Todas as contribuições citadas acima tiveram aplicação prática na industria aeronáutica, sendo utilizadas na implementação de uma metodologia inovadora para acoplar um simulador de escoamento de fluidos tridimensional com uma ferramenta de projeto inverso de aerofólios que roda em um contexto bidimensional. O outro assunto abordado e o remalhamento de triangulações superficiais. Foi proposto um novo método, chamado ANTS (Anisotropic Triangulations on Surfaces) que produz triangulações anisotrópicas de qualidade sobre superfícies descrevendo objetos com geometria complexa. O método ANTS é caracterizado por efetuar o remalhamento diretamente na triangulação inicial, isto é, ele não faz uso de qualquer tipo de parametrização, seja global ou local. O processo de remalhamento é feito por meio de quatro operadores: inserção, remoção e movimento de vértices e alternância de arestas. Os operadores de inserção e remoção de vértices possibilitam controlar a densidade de vértices no domínio, permitindo que nós sejam inseridos em regiões com densidade baixa ou eliminados onde a densidade é alta. A qualidade dos triângulos é controlada por meio dos operadores de movimento de vértices e de alternância (flipping) de arestas. O operador de movimento é utilizado no núcleo do processo de remalhamento. Para evitar que o remalhamento danifique a forma original da superfície, as quinas e os córneres são detectados no inicio do processo e preservados durante o remalhamento. A densidade de vértices sobre o domínio é controlada por uma função de espalhamento. Tal função pode ser passada como entrada para o ANTS ou calculada pelo próprio método. O ANTS foi aplicado com êxito em diversos exemplos gerando malhas de boa qualidade / This thesis intends to make a contribution on the field of dynamic meshes. Dynamic meshes are commonly used in the simulation of problems on domains whose geometry varies in time. Virtual springs are placed in the mesh to rearrange its vertices whenever the domain is changed. The most commonly used types of springs are: longitudinal, torsional and semi-torsional. In this thesis a new type of spring is introduced, the height spring, that is conceptually simple but produces good results. Another contribution of this thesis is the active vertices mechanism, that can improve the CPU processing time of the dynamic mesh. When the mesh domain undergoes large deformations, the proposed dynamic mesh algorithm may fail in correcting the mesh. A solution to this problem is perform large deformations in smal steps. A new strategy for this purpose is presented. Sometimes the motion of the mesh boundary can damage cells on the boundary itself. This is a trick problem to solve since the correction of boundary might change the domain geometry. A new method to correct the boundary cells is also presented in this study. The method is based on the dynamic mesh concept and uses a new type of spring, the conservative spring. All the mentioned contributions had been applied in the aeronautics industry. The techniques developed here has been used to implement an innovative methodology to couple a three-dimensional fluid dynamic solver with a two-dimensional inverse design tool for airfoils. This thesis also deals with remeshing. It is presented the ANTS, a practical method for remeshing anisotropic triangulations on surfaces of complex geometry. The method is capable of performing refinement and coarsening during the same process using the well-known remeshing operators: vertex motion, vertex deletion (by collapsing edges), vertex insertion, and edge flipping. An interesting feature is that vertex motion is used in the core of the process instead of in a post-processing smoothing step. The ANTS uses the input mesh as the geometrical description and works directly on the surface mesh without using any other auxiliary structure (besides the input mesh itself) to preserve the geometrical shape. Moreover, neither global nor local parameterization are applied. Sharp edges and points are identified at the beginning and kept during the process in order to preserve ridges and details. The method has been successfully applied to several examples producing high quality meshes

GraphQL is a database handling API created by Facebook, that provides an effective al-ternative to REST-style architectures. GraphQL provides the ability for a client to spec-ify exactly what data it wishes to receive. A problem with GraphQL is that the freedomof creating customized requests allows data to be included several times in the response,growing the response’s size exponentially. The thesis contributes to the field of GraphQLanalysis by studying the prevalence of simple cycles in GraphQL schemas. We have im-plemented a locally-run tool and webtool using Tarjan’s and Johnson’s algorithms, thatparses the schemas, creates a directed graph and enumerates all simple cycles in the graph.A collection of schemas was analysed with the tool to collect empirical data. It was foundthat 39.73 % of the total 2094 schemas contained at least one simple cycle, with the averagenumber of cycles per schema being 4. The runtime was found to be on average 11 mil-liseconds, most of which consisted of the time for parsing the schemas. It was found that44 out of the considered schemas could not be enumerated due to containing a staggeringamount of simple cycles. It can be concluded that it is possible to test schemas for cyclicityand enumerate all simple cycles in a given schema efficiently.

Orientador: Prof. Dr. Daniel Morgato Martin / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciências da Computação, 2014. / Neste trabalho estudamos o Problema do Isomorfismo de Grafos e a sua complexidade para resolvê-lo. Nossa principal contribuição é a proposta de um algoritmo para o caso geral do Problema, baseado no particionamento do conjunto de vértices e em emparelhamentos perfeitos de grafos bipartidos. Estudamos também o algoritmo de Brendan McKay, que é o mais rápido algoritmo para o Problema do Isomorfismo de Grafos conhecido. Ao final, implementamos o algoritmo proposto nesta dissertação e o algoritmo de McKay. Após a comparação dos dois algoritmos, verificamos que os resultados obtidos pelo algoritmo proposto não foram satisfatórios, porém apresentamos possíveis melhorias de como deixá-lo mais eficiente. / In this work we study the Graph Isomorphism Problem and their complexity to solve it. Our main contribution is to propose an algorithm for the general case of the Problem, based on partitioning the set vertex and perfect matchings of bipartite graphs. We also studied the Brendan McKay¿s algorithm, who is the fastest algorithm for the Graph Isomorphism Problem known. At the end, we implemented the algorithm proposed in this dissertation and McKay¿s algorithm. After comparison of the two algorithms, we found that the results obtained by the proposed algorithm were not satisfactory, but improvements are possible as to make it more efficient.