published_or_final_version / abstract / toc / Computer Science and Information Systems / Master / Master of Philosophy

A computer algorithm is developed for clipping and capping N-sided polyhedra with arbitrary planes. The algorithm is then expanded to include the processing of general two and three dimensional geometric finite element model data. Data processing is included for the transformation of original model results to match the clipped and capped graphical display model. The algorithms are implemented in a FORTRAN program that may be directly substituted into the MOVIE.BYU/ARIZONA graphics system. The new SECTION program maintains all the functions of the original version while incorporating several major new features. These new features include the expansion of the geometric library to two and three dimensional elements and two new general forms for polygons and polyhedra. Another significant change in the processing is the implementation of the reentrant clipping and capping routines. This feature permits a previously clipped model to be clipped again and again by new and different clipping planes. The above features as well as enhanced input data schemes including a preliminary interface to NASTRAN are offered as a skeleton for future modifications. The major routines in the program have taken advantage of dynamic memory allocation via FORTRAN subroutine argument calls. Through this latter feature new capability can be concatenated to the end of the current processing in a prototype manner for rapid implementation and exploration.

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-03-22Bitstream added on 2014-06-13T20:35:10Z : No. of bitstreams: 1 ferreira_fe_me_sjrp.pdf: 904891 bytes, checksum: 189144772384df69733ce1617b84cb5d (MD5) / De acordo com as atuais diretrizes pertinentes ao ensino de matemática (Parâmetros Curriculares Nacionais : Matemática e Proposta Curricular do Estado de São Paulo: Matemática), este trabalho baseia-se na Teoria de Van Hiele, visando a aprendizagem de conceitos geométricos, em particular a aprendizagem de poliedros regulares, através da confecção de dobraduras (origami). Iniciando com uma abordagem histórica sobre poliedro, apresenta orientações para o uso de origami em sala de aula, delineia as principais características da Teoria de Van Hiele, além de retomar os principais conceitos matemáticos associados aos poliedros. Utilizando este arcabouço é proposta uma sequência de atividades de sondagem e aplicação de conceitos geométricos respeitando as fases de aprendizagem de Van Hiele, visando a conclusão por parte do aluno, da existência de apenas cinco poliedros regulares. Após a execução das atividades propostas, as demonstrações dos teoremas relacionados aos poliedros apresentados neste trabalho servirão para a sistematização das conclusões feitas pelos alunos, sempre respeitando o nível de Van Hiele em que se encontrem. Apresenta, ainda, atividades de exploração das características dos poliedros através do Teorema de Euler para poliedros convexos / According to the current guidelines relevant to teaching mathematics (National Curriculum: Mathematics, and Curricular Proposal of the State of São Paulo: Mathematics) this work is based on Van Hiele, and aimed at learning of geometric concepts, particularly learning regular polyhedra, by paperfolding (origami). Starting with a historical approach of polyhedron, this work presents guidelines for the use of origami in the classroom, outlines the main features of the Van Hiele theory, and resume the main mathematical concepts associated with polyhedra. Using this framework, a sequence of activities is proposed and the applying of geometric concepts respecting the learning phases of Van Hiele, which aims deduction by the student, of the existence of only five regular polyhedra. After execution of the proposed activities, the proof of theorems related to polyhedra presented in this paper will serve to systematize the conclusions made by the students, always respecting the level of Van Hiele who are. It presents further exploration of the characteristics of polyhedra by Euler's theorem for convex polyhedra

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Polyhedra are geometric solids formed by a finite number of polygons they can be convex or non-convex, regular or not regular. This work we make three demonstrations of Eulerâs theorem for polyhedra in one plane being used graphs. We will adopt preliminary definitions of polygons, polyhedra and graphs and make a brief study of the theorem before the demonstrations analysis when the theorem is valid and what conditions exist polyhedra, since the theorem is accepted. The work brings some applications in the form of questions in the theory presented. / Os poliedros sÃo sÃlidos geomÃtricos formados por uma quantidade finita de polÃgonos. Eles podem ser convexos ou nÃo convexos, regulares ou nÃo regulares . Neste trabalho fazemos trÃs demonstraÃÃes do teorema de Euler para poliedros no plano, sendo uma utilizado grafos. Adotaremos definiÃÃes preliminares de polÃgonos, poliedros e grafos e faremos um breve estudo do teorema antes das demonstraÃÃes analisado quando o teorema à valido em quais condiÃÃes existem os poliedros, uma vez que o teorema à aceito. O trabalho traz algumas aplicaÃÃes em forma de questÃes da teoria apresentada.

Uma das questões mais importantes em Teoria de Singularidades é a determinação de condições que garantam a trivialidade topológica em famílias de germes de funções ou aplicações. Neste trabalho é feito um estudo a fim de descrever condições necessárias e suficientes para a trivialidade topológica em famílias de germes de funções com singularidade isolada. Para isto, são apresentados dois métodos. O primeiro é o de campos de vetores controlados, baseado nos trabalhos de Damon-Gaffney e Yoshinaga. O segundo relaciona invariantes associados às famílias de germes de funções com a trivialidade topológica destas. Em ambos os casos, a principal ferramenta é a construção de poliedros de Newton associados às famílias. / One of the most important questions in Theory of Singularities is the determination of conditions that guarantee the topological triviality in families of germs of functions or mappings. In this work a study is made in order to describe necessaries and sufficients conditions for the topological triviality in families of germs of functions with isolated singularity. For this, two methods are presented. The first one is controlled vectors fields method, based on the works of Damon-Gaffney and Yoshinaga. The second relates invariants associated with families of germs of functions with the topological triviality of these. In both cases, the main tool used is the construction of Newton polyhedra associated with families.

In this work, we focus on two kinds of problems involving the proximity of geometric objects. The first part revolves around intersection detection problems. In this setting, we are given two (or more) geometric objects and we are allowed to preprocess them. Then, the objects are translated and rotated within a geometric space, and we need to efficiently test if they intersect in these new positions. We develop representations of convex polytopes in any (constant) dimension that allow us to perform this intersection test in logarithmic time.In the second part of this work, we turn our attention to facility location problems. In this setting, we are given a set of sites in a geometric space and we want to place a facility at a specific place in such a way that the distance between the facility and its farthest site is minimized. We study first the constrained version of the problem, in which the facility can only be place within a given geometric domain. We then study the facility location problem under the geodesic metric. In this setting, we consider a different way to measure distances: Given a simple polygon, we say that the distance between two points is the length of the shortest path that connects them while staying within the given polygon. In both cases, we present algorithms to find the optimal location of the facility.In the process of solving facility location problems, we rely heavily on geometric structures called Voronoi diagrams. These structures summarize the proximity information of a set of ``simple'' geometric objects in the plane and encode it as a decomposition of the plane into interior disjoint regions whose boundaries define a plane graph. We study the problem of constructing Voronoi diagrams incrementally by analyzing the number of edge insertions and deletions needed to maintain its combinatorial structure as new sites are added. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Après une présentation générale des cartes planaires, nous définissons les polyèdres en coin, étudiés par Eppstein et Mumford. Nous en venons rapidement à introduire les triangulations en coin, qui sont les cartes duales des squelettes des polyèdres en coin, et en donnons quelques propriétés. Nous proposons un algorithme de réalisation de polyèdres en coin de complexité linéaire. Pour cela, l'étude des triangulations en coin conduit à des problèmes d'énumération. Une méthode classique, connue depuis Tutte, donne le résultat voulu en faisant intervenir la série des nombres de Catalan. La recherche d'une explication combinatoire à la présence des nombres de Catalan a rendu souhaitable l'utilisation d'autres méthodes, fondées sur des découpages et des recollements de morceaux de triangulations en coin. Ainsi apparaît la famille des triangulations en amande, qui est une nouvelle représentation des nombres de Catalan, qui est en bijection directe avec la famille des arbres binaires, et qui complète notre algorithme de réalisation de polyèdres en coin. Nous apportons enfin une conclusion à ces travaux en tentant de généraliser nos méthodes à des cartes dont les faces sont de degré fixé, mais quelconque. / After a general presentation of planar maps, we define corner polyhedra, studied by Eppstein and Mumford. We soon introduce corner triangulations, that are dual maps of the skeletons of corner polyhedra, and we give some properties of them.We offer a linear time algorithm to realize corner polyhedra. For that, the study of corner triangulations leads to enumeration problems. A classic method, known from Tutte, gives the wanted result, making the series of Catalan numbers appearing. The research for a combinatorial explanation of the presence of Catalan numbers induces the use of other methods, based on cuttings and gluings of some parts of corner triangulations. Thus appears the family of almond triangulations, that is a new representation of Catalan numbers, in bijection with the binary trees family, and that completes our corner polyhedra realization algorithm. We eventually give a conclusion to these works, trying to generalize our methods to maps whose faces have an any fixed degree.

No description available.

In this thesis, we propose and study discrete, multi-period extensions of classical packing problems, a fundamental class of models in combinatorial optimization. Those extensions fall under the general name of incremental packing problems. In such models, we are given an added time component and different capacity constraints for each time. Over time, capacities are weakly increasing as resources increase, allowing more items to be selected. Once an item is selected, it cannot be removed in future times. The goal is to maximize some (possibly also time-dependent) objective function under such packing constraints. In Chapter 2, we study the generalized incremental knapsack problem, a multi-period extension to the classical knapsack problem. We present a policy that reduces the generalized incremental knapsack problem to sequentially solving multiple classical knapsack problems, for which many efficient algorithms are known. We call such an algorithm a single-time algorithm. We prove that this algorithm gives a (0.17 - ⋲)-approximation for the generalized incremental knapsack problem. Moreover, we show that the algorithm is very efficient in practice. On randomly generated instances of the generalized incremental knapsack problem, it returns near optimal solutions and runs much faster compared to Gurobi solving the problem using the standard integer programming formulation. In Chapter 3, we present additional approximation algorithms for the generalized incremental knapsack problem. We first give a polynomial-time (½-⋲)-approximation, improving upon the approximation ratio given in Chapter 2. This result is based on a new reformulation of the generalized incremental knapsack problem as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys-Tardos algorithm for the generalized assignment problem. Using the same sequencing reformulation, combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we give a quasi-polynomial time approximation scheme for the problem, thus ruling out the possibility that the generalized incremental knapsack problem is APX-hard under widely-believed complexity assumptions. In Chapter 4, we first turn our attention to the submodular monotone all-or-nothing incremental knapsack problem (IK-AoN), a special case of the submodular monotone function subject to a knapsack constraint extended to a multi-period setting. We show that each instance of IK-AoN can be reduced to a linear version of the problem. In particular, using a known PTAS for the linear version from literature as a subroutine, this implies that IK-AoN admits a PTAS. Next, we study special cases of the generalized incremental knapsack problem and provide improved approximation schemes for these special cases. In Chapter 5, we give a polynomial-time (¼-⋲)-approximation in expectation for the incremental generalized assignment problem, a multi-period extension of the generalized assignment problem. To develop this result, similar to the reformulation from Chapter 3, we reformulate the incremental generalized assignment problem as a multi-machine sequencing problem. Following the reformulation, we show that the (½-⋲)-approximation for the generalized incremental knapsack problem, combined with further randomized rounding techniques, can be leveraged to give a constant factor approximation in expectation for the incremental generalized assignment problem. In Chapter 6, we turn our attention to the incremental knapsack polytope. First, we extend one direction of Balas's characterization of 0/1-facets of the knapsack polytope to the incremental knapsack polytope. Starting from extended cover inequalities valid for the knapsack polytope, we show how to strengthen them to define facets for the incremental knapsack polytope. In particular, we prove that under the same conditions for which these inequalities define facets for the knapsack polytope, following our strengthening procedure, the resulting inequalities define facets for the incremental knapsack polytope. Then, as there are up to exponentially many such inequalities, we give separation algorithms for this class of inequalities.

Ph. D.