[pt] O eixo medial é uma descrição compacta de um objeto que preserva sua topologia e induz naturalmente uma discretização da sua forma como união de bolas. O estudo de união de bolas possui aplicações em diversas áreas da Matemática, em particular na Geometria Computacional onde se usa, por exemplo, para reconstrução de curvas e superfícies. Este trabalho pretende utilizar união de bolas para simular deformações a partir do eixo medial, apresentando conceitos e teoremas a fim de construir algoritmos para a extração do eixo medial em R3. A deformação será, então, definida por movimentos locais das bolas ao longo das direções do eixo medial. Este trabalho contém resultados com movimentos simples, em um programa que utiliza a biblioteca CGAL / [en] The medial axis is a compact description of an object that preserves its topology and naturally induces a discretisation of its forma in terms of union of balls. The study of union of balls has applications in various areas of Mathematics, in particular in Computational Geometry where it is used for curve and surface reconstruction. This work pretends to use union of balls in order to simulate deformations described on the medial axis. It introduces concepts and theorems in order to setup algorithms for medial axis extraction in R3. The deformation will thus be defined by local ball moves along the medial axis directions. This work contains results with simple movements, in a program that uses the CGAL library

[pt] O estudo computacional de uniões de bolas possui aplicações em diversas áreas da Matemática. O objetivo principal deste trabalho é propor uma simplificação de união de bolas em R2 através de um movimento que obedece as direções do eixo medial, procurando preservar os grandes elementos geométricos da união de bolas. A desconexão ou não das formas é um aspecto essencial da evolução. Em alguns casos, pode significar uma divisão importante do objeto. Em outros, pode ser indesejada, pois gostaríamos de ter uma versão conexa simplificada da forma. / [en] The computational study of unions of balls has applications in several domains of the Mathematics. The purpose of this dissertation is to propose a simplification of the union of balls in R2 through a movement that obeys the direction of the medial axis in order to simplify it, maintaining the major geometric elements of its shape. The disconnection of the shape is an essential property of the evolution. In some cases, it could mean an important division of the object. In others, it may be undesirable because we would like to have a simplified version connected of this shape.

Représenter un objet géométrique complexe par un ensemble de primitives simples est une tâche souvent fondamentale, que ce soit pour la reconstruction et la réparation de données, ou encore pour faciliter la visualisation ou la manipulation des données. Le choix de la ou les primitives, ainsi que celui de la méthode d'approximation, impactent fortement les propriétés de la représentation de forme qui sera obtenue.Dans cette thèse, nous utilisons les boules comme seule primitive. Nous prenons ainsi un grand soin à décrire les unions finies de boules et leur structure. Pour cela, nous nous reposons sur les faisceaux de boules. En particulier, nous aboutissons à une description valide en toute dimension, sans hypothèse de position générale. En chemin, nous obtenons également plusieurs résultats portant sur les tests d'inclusion locale et globale dans une union de boules.Nous proposons également une nouvelle méthode d'approximation par union finie de boules, l'approximation par boules à (delta,epsilon)-près. Cette approche contraint l'union de boules à couvrir un sous-ensemble de la forme d'origine (précisément, un epsilon-érodé), tout en étant contenu dans un sur-ensemble de la forme (un delta-dilaté). En nous appuyant sur nos précédents résultats portant sur les unions de boules, nous démontrons plusieurs propriétés de ces approximations. Nous verrons ainsi que calculer une approximation par boules à (delta,epsilon)-près qui soit de cardinal minimum est un problème NP-complet. Pour des formes simples dans le plan, nous présentons un algorithme polynomial en temps et en espace qui permet de calculer ces approximations de cardinal minimum. Nous concluons par une généralisation de notre méthode d'approximation pour une plus large variété de sous-ensembles et sur-ensembles. / Describing a complex geometric shape with a set of simple primitives is often a fundamental task for shape reconstruction, visualization, analysis and manipulation. The type of primitives, as well as the choice of approximation scheme, both greatly impact the properties of the resulting shape representation.In this PhD, we focus on balls as primitives. Using pencils of balls, we carefully describe finite unions of balls and their structure. In particular, our description holds in all dimension without assuming general position. On our way, we also establish various results and tools to test local and global inclusions within these unions.We also propose a new approximation scheme by union of balls, the (delta,epsilon)-ball approximation. This scheme constrains the approximation to cover a core subset of the original shape (specifically, an epsilon-erosion), while being contained within a superset of the shape (a delta-dilation). Using our earlier results regarding finite unions of balls, we prove several properties of these approximations. We show that computing a cardinal minimum (delta,epsilon)-ball approximation is an NP-complete problem. For simple planar shapes however, we present a polynomial time and space algorithm that outputs a cardinal minimum approximation. We then conclude by generalizing the approximation scheme to a wider range of core subsets and bounding supersets.