[pt] Apresenta-se nesta dissertação um novo algoritmo para o cálculo de algumas funções distância entre polígonos convexos, no caso geral em que os polígonos podem se interseptar, cuja complexidade linear de pior caso é melhor do que a dos algoritmos até então conhecidos na literatura. O algoritmo é baseado em um algoritmo de complexidade linear originalmente proposto para determinação da distância de Hausdorff entre polígonos convexos disjuntos e utiliza como sua principal componente um algoritmo linear para o cálculo da interseção entre polígonos convexos. A motivação para o estudo de algoritmos eficientes para este problema de cálculo de distâncias decorre de aplicações em reconhecimento de formas e superposição ótima de contornos. Resultados computacionais também são apresentados. / [en] We present in this dissertation a new algorithm for the computation of some distance functions between convex polygons, in the general case where they can intersect, whose worst case time complexity is better than of the previously known algorithms. The algorthm is based on an algorithm originally proposed for the computation of the Hausdorff distance between disjoint polygons and uses as its main component a linear time algorithm for finding the intersection of convex polygons. The motivation for the study of efficient algorithms for this distance computation problem comes from applications in pattern recognition and contour fitting. Computatioal results are also presented.

This thesis covers the development process of implementation, and evaluation of a softbody physics engine for convex polygon objects. The main feature is implementation of adynamic polygon collider that represents a polygons shape correctly, while still being ableto collide with other objects in the simulation. Objects are able to deform both temporarily and permanently using springs with distance constraints. Pressure simulation is alsoimplemented to simulate inflated polygons. The physics bodies does not feature frictionbetween objects, only friction against a static boundary of the simulation. The engine isthen evaluated in order to determine if it can run in real-time which is one of the goals.When it comes to the simulation, Verlet-integration will be used for updating the positions of particles, and every polygon will be built using these particles, and combinedusing certain constraints to make the particles act as one combined object. The main problem that will be solved is the interpenetration solver, which ensures that polygons do notoverlap, and two formulas will be combined to solve this problem. The collision detectionmethod uses line intersections to determine if objects are overlapping, this method endedup being quite expensive for polygons with a lot of vertices. One optimization techniqueis implemented which is axis-aligned bounding boxes around objects which improvedperformance significantly, which also makes the engine more viable for real-time simulations. The physics engine in this report is deterministic using a fixed time-step, dynamictime-step is not tested. The engine also only supports discrete collision detection.

No description available.

In this thesis we consider extensions and generalizations of some classical problems in Combinatorial Geometry. Our work is an offshoot of four classical problems in Combinatorial Geometry. A fundamental assumption in these problems is that the underlying point set is R2. Two fundamental themes entwining the problems considered in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since. Avis et al. in 2001 posed the following question which we call the n-interior point problem: Is there a finite integer g(n) for every n, such that, every point set P with g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset which is a convex polygon that contains exactly n interior points. They showed that g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers. We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed the following fundamental question which can be considered as a generalised version of Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known. Inspired by the original question of Danzer and Gr¨unbaum we consider their question in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting. In the third part of this thesis, we broadly look at hitting and covering questions with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively. These problems has been well studied in the case when P = R2. We systematically look at the case when P is finite, showing bounds for intervals, halfspaces, orthants, unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2. Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express the bound on the size of the set Q in terms of ǫ. Let G be a uniform √n × √n grid. It is an intriguing question as to whether we get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.

Dans ce mémoire de thèse, on étudie le morphisme de monoïde $mu$du monoïde libre sur l'alphabet des entiers $nb$,`a valeurs dans le groupe modulaire $PSL_2(zb)$,considéré comme monoïde, défini pour tout entier $a$ par $mu(a)=begin{pmatrix} 0 & -1 1 & a+1 end{pmatrix}.$Les nombres de Catalan apparaissent naturellement dans l'étudede sous-ensembles du noyau de $mu$.Dans un premier temps, on met en évidence deux systèmes de réécriture, l'un sur l'alphabet fini ${0,1}$, l'autresur l'alphabet infini des entiers $nb$ et on montreque ces deux systèmes de réécriture définissent des présentations de monoïde de $PSL_2(zb)$ par générateurs et relations.Par ailleurs, on introduit le morphisme d'indice associé `a l'abélianisé du rev^etement universel de $PSL_2(zb)$,le groupe $B_3$ des tresses `a trois brins. Interprété dans deux contextes différents,le morphisme d'indice est associé au nombre de "demi-tours".Ensuite, dans les quatrième et cinquième parties, on dénombre des sous-ensembles du noyau de $mu_{|{0,1}}$ etdu noyau de $mu$, bigradués par la longueur et l'indice. La suite des nombres de Catalan et d'autres diagonales du triangle de Catalan interviennentsimplement dans les résultats.Enfin, on présente l'origine géométrique de cette étude : on explicite le lien entre l'objectif premier de la thèse qui était l'étudedes polygones convexes entiers d'aire minimale et notre intéret pour le monoïde engendré par ces matrices particulières de $PSL_2(zb)$. / In this thesis, we study a morphism of mono"id $mu$ between the free mono"id on the alphabet of integers $nb$and the modular group $PSL_2(zb)$ considered as a mono"id, defined for all integer $a$by $mu(a)=begin{pmatrix} 0 & -1 1 & a+1 end{pmatrix}.$ The Catalan Numbers arised naturally in the study ofsubsets of the kernel of the morphism $mu$.Firstly, we introduce two rewriting systems, one on the finite alphabet ${0,1}$, and the other on the infinite alphabet of integers $nb$. We proove that bothof these rewriting systems defines a mono"id presentation of $PSL_2(zb)$ by generators and relations.On another note, we introduce the morphism of loop associated to the abelianised of the universal covering group of $PSL_2(zb)$, the group $B_3$ ofbraid group on $3$ strands. In two different contexts, the morphism of loop is associated to the number of "half-turns".Then, in the fourth and the fifth parts, we numerate subsets of the kernel of $mu_{|{0,1}}$ and of the kernel of $mu$,bi-graduated by the morphism of lengthand the morphism of loop. The sequences of Catalan numbers and other diagonals of the Catalan triangle come into the results.Lastly, we present the geometrical origin of this research : we detail the connection between our first aim,which was the study of convex integer polygones ofminimal area, and our interest for the mono"id generated by these particular matrices of $PSL_2(zb)$.

Cette thèse se compose de plusieurs travaux portant sur l'énumération et le comportement asymptotique de structures combinatoires apparentées aux partitions d'entiers. Un premier travail s'intéresse aux partitions d'entiers bipartites, qui constituent une généralisation bidimensionnelle des partitions d'entiers. Des équivalents du nombre de partitions sont obtenus dans le régime critique où l'un des entiers est de l'ordre du carré de l'autre entier et au delà de ce régime critique. Ceci complète les résultats établis dans les années cinquante par Auluck, Nanda et Wright. Le deuxième travail traite des chaînes polygonales à sommets entiers dans le plan. Pour un modèle statistique introduit par Sinaï, une représentation intégrale exacte de la fonction de partition est donnée. Ceci conduit à un équivalent du nombre de chaînes joignant deux points distants qui fait intervenir les zéros non triviaux de la fonction zêta de Riemann. Une analyse combinatoire détaillée des chaînes convexes est présentée. Elle permet de montrer l'existence d'une forme limite pour les chaînes convexes aléatoires ayant peu de sommets, répondant ainsi à une question ouverte de Vershik. Un troisième travail porte sur les zonotopes à sommets entiers en dimension supérieure. Un équivalent simple est donné pour le logarithme du nombre de zonotopes contenus dans un cône convexe et dont les extrémités sont fixées. Une loi des grands nombres est établie et la forme limite est caractérisée par la transformée de Laplace du cône. / This thesis consists of several works dealing with the enumeration and the asymptotic behaviour of combinatorial structures related to integer partitions. A first work concerns partitions of large bipartite integers, which are a bidimensional generalization of integer partitions. Asymptotic formulæ are obtained in the critical regime where one of the numbers is of the order of magnitude of the square of the other number, and beyond this critical regime. This completes the results established in the fifties by Auluck, Nanda, and Wright. The second work deals with lattice convex chains in the plane. In a statistical model introduced by Sinaï, an exact integral representation of the partition function is given. This leads to an asymptotic formula for the number of chains joining two distant points, which involves the non trivial zeros of the Riemann zeta function. A detailed combinatorial analysis of convex chains is presented. It makes it possible to prove the existence of a limit shape for random convex chains with few vertices, answering an open question of Vershik. A third work focuses on lattice zonotopes in higher dimensions. An asymptotic equality is given for the logarithm of the number of zonotopes contained in a convex cone and such that the endings of the zonotope are fixed. A law of large numbers is established and the limit shape is characterized by the Laplace transform of the cone.