This bachelor's thesis is a part of a larger project carried out at Paradox Interactive. The project aims to improve a map generator for the strategy game Europa Universalis IV. This work addresses the creation and implementation of a province generator that divides a pregenerated landscape in provinces. The provinces in the game are the regions on the game map that the game mechanics are based upon. The improvements that are expected of the new province generator includes the following properties: • The provinces that are created have more logically placed boundaries that are affected by the structure of the landscape. • The program gives the user more control over how the end result should look like by letting the user set the values of input parameters. • The execution should not exceed an approximate time limit. This time limit is set by Paradox Interactive. The work began with research on the topics map creation and map division to give enough knowledge to plan the implementation of the program. The programming language that is used is Java. The implementation of the program is based on many well-known algorithms in which the most remarkable one is Fortune's algorithm which performs the main task of the provincial division of the program, the creation of Voronoi diagrams. The Voronoi diagrams are used to divide the map into regions which by using a post-process results in the creation of the provinces. Other well-known algorithms and methods used or addressed in this report include the Lloyd relaxation, Bresenham's line algorithm, Scan Line Flood Fill, Delaunay triangulation and Bowyer-Watson's algorithm. The result of this work is a Java application that can load a map file containing information of a landscape structure and create a division of provinces with provincial boundaries that depend on the structure of the landscape. The results of the provincial division may be controlled by a number of user defined parameters. The program could not be fully calibrated during the time of the project because the landscape generator was not ready in time to be able to provide a map of a generated landscape. The generated provinces can be saved as an image file on the hard disk. / Kandidatexamensarbetet är en del av ett större projekt som utförs på företaget Paradox Interactive. Projektets mål är att förbättra en kartgenerator för strategispelet Europa Universalis IV. Det här arbetet avser skapandet och implementationen av en provinsgenerator som delar in ett färdiggenererat landskap i provinser. Provinserna i spelet är de landsdelar på kartan som spelmekaniken bygger på. Förbättringarna som förväntas av den nya provinsgeneratorn är bland annat att: • Provinserna som skapas ska ha mer logiska gränser som påverkas av landskapets utformning och inte vara alltför orealistiska. • Ge användaren mer kontroll över hur slutresultatet ska se ut genom användarinmatade parametrar. • Inte överstiga en ungefärlig tidsgräns vid programmets exekvering. Tidsgränsen sätts av Paradox Interactive. Arbetet började med forskning kring ämnena kartgenerering och kartindelning vilket gav tillräckligt med kunskap för att planera hur programmet skulle implementeras. Programmeringsspråket som används är Java. Implementationen av programmet bygger på många kända algoritmer där den mest anmärkningsvärda algoritmen är Fortune's algoritm som utför huvuduppgiften för provinsindelningen i programmet, skapandet av Voronoidiagram. Voronoi-diagramen används för att dela in kartan i ytor som med hjälp av en postprocess resulterar i skapandet av provinserna. Andra kända algoritmer och metoder som används eller tas upp i den här rapporten är bland annat Lloyd relaxation, Bresenham's linjealgoritm, Scanline floodfill, Delaunay triangulering och Bowyer–Watson's algoritm. Resultatet av arbetet är ett Java-program som kan läsa in en kartfil med information om landskapsstruktur och skapa en indelning av provinser med provinsgränser som beror på landskapets utformning. Resultatet av provinsindelningen kan styras med hjälp av ett antal användarinmatade parametrar. Programmet hann inte kalibreras fullt ut under arbetets gång på grund av att landskapsgeneratorn inte blev färdig i tid för att kunna bidra med en genererad landskapskarta. De genererade provinserna kan sparas som en bildfil på hårddisken.

With the rise of accessible, affordable, and portable scanning technologies, new possibilities of making scanning real world objects available for a wider range of applications have emerged. Together with the advancements made in making point set processing and surface reconstruction effcient and easily implementable, it may be possible to combine these to make a portable scanner that produces 3D representations of real world objects that are usable for game development purposes. This thesis explores to what extent surface reconstructions created from point sets gathered with Google Tango is useful in game development processes. To explore this, a mobile application and a software program have been iteratively developed and evaluated through a user study. The results suggest that the surface reconstruction may be useful in the development of a game engine project as a basis for creating models on top of. / Med ökningen av tillgängliga, prisvärda och bärbara skanningsteknologierhar nya möjligheter att göra skanning av riktiga objekt tillgängligtför ett brett spektrum av applikationer uppstått. Tillsammans medde framsteg som gjorts för att göra punktmolnsbearbetning och ytrekonstruktionereffektiva och lätt implementerbara kan det vara möjligtatt kombinera dessa för att skapa en bärbar skannare som producerar3D-representationer av verkliga objekt som kan användas förspelutvecklingsändamål. Denna avhandling undersöker i vilken utsträckningytrekonstruktioner som skapats från punktmoln som samlatsmed Google Tango är användbara i spelutvecklingsprocesser. Föratt utforska detta har en mobilapplikation och ett program utvecklatsiterativt och utvärderats med hjälp av en användarstudie. Resultatentyder på att ytrekonstruktionerna kan vara användbara vid utvecklingenav ett spelmotorsprojekt, men som grund för att skapa modellerutifrån.

Spatial data arises in applications such as geographical information systems, computer aided design and computer vision. A practical indexing method for spatial data is the R-tree [1]. A common query to an R-tree is a window query which outputs all spatial objects that intersect a rectangular region in space. The PR-tree is the first R-tree variant where window query performance is asymptotically optimal in the worst case. In this work a PR-tree is updated using algorithms defined by Antonin Guttman [2] and Beckmann et al. [3], respectively and query performance is evaluated. The conclusion is that the R*-tree algorithms by Beckmann et al. [3] is superior to the algorithms by Antonin Guttman [2] for maintaining good query performance while updating a PR-tree / Spatial data är vanligt förekommande i geografiska informationssystem, CAD och datorseende. Ett praktiskt index för spatial data är ett R-träd [1]. En vanlig sökfråga till ett R-träd är en så kallad window query som ges ett rektangulärt område och returnerar alla spatiala objekt som skär detta område. PR-trädet är det första R-trädet med asymptotiskt optimal tidskomplexitet för en window query. I detta arbete används PR-trädet som bas och det modifieras med respektiva algoritmer definerade av Antonin Guttman [2] och Beckmann m. fl. [3] och prestanda för rektangulära sökfrågor utvärderas. Slutsatsen är att om målet är att bibehålla bra prestanda för sökfrågor medan PR-trädet modifieras ska algoritmerna av Beckmann m. fl. [3] föredras.

No description available.

This thesis addresses the multi-body assembly (MBA) problem in the context of protein assemblies. [...] In this thesis, we chose the protein assembly domain because accurate and reliable computational modeling, simulation and prediction of such assemblies would clearly accelerate discoveries in understanding of the complexities of metabolic pathways, identifying the molecular basis for normal health and diseases, and in the designing of new drugs and other therapeutics. [...] [We developed] F²Dock (Fast Fourier Docking) which includes a multi-term function which includes both a statistical thermodynamic approximation of molecular free energy as well as several of knowledge-based terms. Parameters of the scoring model were learned based on a large set of positive/negative examples, and when tested on 176 protein complexes of various types, showed excellent accuracy in ranking correct configurations higher (F² Dock ranks the correcti solution as the top ranked one in 22/176 cases, which is better than other unsupervised prediction software on the same benchmark). Most of the protein-protein interaction scoring terms can be expressed as integrals over the occupied volume, boundary, or a set of discrete points (atom locations), of distance dependent decaying kernels. We developed a dynamic adaptive grid (DAG) data structure which computes smooth surface and volumetric representations of a protein complex in O(m log m) time, where m is the number of atoms assuming that the smallest feature size h is [theta](r[subscript max]) where r[subscript max] is the radius of the largest atom; updates in O(log m) time; and uses O(m)memory. We also developed the dynamic packing grids (DPG) data structure which supports quasi-constant time updates (O(log w)) and spherical neighborhood queries (O(log log w)), where w is the word-size in the RAM. DPG and DAG together results in O(k) time approximation of scoring terms where k << m is the size of the contact region between proteins. [...] [W]e consider the symmetric spherical shell assembly case, where multiple copies of identical proteins tile the surface of a sphere. Though this is a restricted subclass of MBA, it is an important one since it would accelerate development of drugs and antibodies to prevent viruses from forming capsids, which have such spherical symmetry in nature. We proved that it is possible to characterize the space of possible symmetric spherical layouts using a small number of representative local arrangements (called tiles), and their global configurations (tiling). We further show that the tilings, and the mapping of proteins to tilings on arbitrary sized shells is parameterized by 3 discrete parameters and 6 continuous degrees of freedom; and the 3 discrete DOF can be restricted to a constant number of cases if the size of the shell is known (in terms of the number of protein n). We also consider the case where a coarse model of the whole complex of proteins are available. We show that even when such coarse models do not show atomic positions, they can be sufficient to identify a general location for each protein and its neighbors, and thereby restricts the configurational space. We developed an iterative refinement search protocol that leverages such multi-resolution structural data to predict accurate high resolution model of protein complexes, and successfully applied the protocol to model gp120, a protein on the spike of HIV and currently the most feasible target for anti-HIV drug design. / text

Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan.Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique. / In this thesis, we study several problems related to the design of geometric networks and isometric embeddings into the plane.We start by considering the generalization of the classical Minimum Manhattan Network problem to all normed planes. We search the minimum network that connects each pair of terminals by a shortest path in this norm. We propose a factor 2.5 approximation algorithm in time O(mn^3), where n is the number of terminals and m is the number of directions of the unit ball.The second problem presented is an oriented version of the minumum Manhattan Network problem, we want to obtain a minimum oriented network such that for each pair u, v of terminals, there is a shortest rectilinear path from u to v and another path from v to u.We describe a factor 2 approximation algorithm with complexity O(n^3) where n is the number of terminals for this problem.Then we study the problem of finding a planar spanner (a subgraph which approximates the distances) of the Unit Disk Graph (UDG) which is used to modelize wireless ad hoc networks. We present an algorithm for computing a constant hop stretch factor planar spanner for all UDG. This algorithm uses only local properties and it can be implemented in distributed manner.Finally, we study the problem of recognizing metric spaces that can be isometrically embbed into the rectilinear plane and we provide an optimal time O(n^2) algorithm to solve this problem. We also study the generalization of this problem to all normed planes whose unit ball is a centrally symmetric convex polygon.

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Este trabalho descreve uma tÃcnica de decomposiÃÃo de domÃnios bidimensionais para geraÃÃo em paralelo de malhas. Esta tÃcnica funciona tanto para memÃria distribuÃda quanto compartilhada, alÃm de permitir que se utilize qualquer estrutura de dados que gere regiÃes quadrangulares paralelas aos eixos para decompor o domÃnio dado como entrada. Pode se utilizar por exemplo, uma Ãrvore quaternÃria (quadtree) ou uma partiÃÃo binÃria do espaÃo (bsp). AlÃm disso, qualquer processo de geraÃÃo de malha que respeite os prÃ-requisitos estabelecidos pode ser empregado nos subdomÃnios criados, como as tÃcnicas de Delaunay ou AvanÃo de Fronteira, dentre outras. A tÃcnica proposta à dita a priori porque a malha de interface entre os subdomÃnios à gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomÃnio à feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nÃvel de refinamento orienta a criaÃÃo das arestas que sÃo definidas a partir da discretizaÃÃo das fronteiras das cÃlulas internas. Essa maneira de estimar carga produz resultados que representam, com boa precisÃo, o nÃmero de elementos a serem gerados em cada subdomÃnio. Isso contribui para um bom particionamento do domÃnio, fazendo com que a geraÃÃo de malha em paralelo seja significativamente mais rÃpida do que a geraÃÃo serial. AlÃm disso, a qualidade da malha gerada em paralelo à qualitativamente equivalente Ãquela gerada serialmente, dentro de limites aceitÃveis. / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits.

We study single-pursuer, line-of-sight Pursuit and Evasion games in polytopes in $\mathbb{R}^n$. We develop winning Pursuer strategies for simple classes of polytopes (monotone prisms) in Rn, using proven algorithms for polygons as inspiration and as subroutines. More generally, we show that any Pursuer-win polytope can be extended to a new Pursuer-win polytope in more dimensions. We also show that some more general classes of polytopes (monotone products) do not admit a deterministic winning Pursuer strategy. Though we provide bounds on which polytopes are Pursuer-win, these bounds are not tight. Closing the gap between those polytopes known to be Pursuer-win and those known not to be remains an problem for future researchers.

La géomodélisation du sous-sol est considérée comme stratégique par les compagnies pétrolières. Chacune a en effet pour objectif de construire les meilleurs modèles géologiques sur lesquels seront évalués les réserves de gaz et d'huile des territoires étudiés, ainsi que le placement optimal des puits de forage qui exploiteront ces réserves. Ces modèles sont bâtis sur l'interprétation de la sismique par les géologues et les géophysiciens. Le processus de modélisation consiste à structurer le sous-sol en un ensemble d'horizons (strates géologiques), de failles (fractures de la roche) et de corps (amas de roches de même nature). Ces objets géologiques sont au sein de deux problématiques complémentaires abordées dans cette thèse chez Total : la construction du modèle structural à proprement parler constitué d'un réseau de failles et d'horizons mis en cohérence et la constructions des corps selon des attributs sismiques élaborés. La construction du modèle structural part des données issues d'interprétations manuelles et/ou semi-automatiques ne décrivant que ponctuellement les objets géologiques : un ensemble de lignes brisées pour les failles et un nuage de points pour les horizons. Une première partie de nos travaux porte sur l'élaboration d'une méthodologie complète de construction de surfaces modélisant les failles et les horizons adaptée à la nature et la densité particulières des données initiales. Dans un premier temps les failles sont reconstruites indépendamment les unes des autres à l'aide d'une triangulation de Delaunay contrainte des données projetées dans leur plan de régression, puis raffinées par subdivision. Ensuite un réseau de failles global est créé et mis en cohérence par des opérations d'extrapolation et de clipping. Enfin, les trous dans les horizons sont bouchés par des méthodes d'interpolation spatiale étendus par nos soins à l'aide des "voisinages partiels" contraints par les failles, pour lesquelles nous montrons l'influence des stratégies de remplissage et leur robustesse au bruit. Les corps sont construits par extraction d'isosurfaces sur des volumes d'attributs sismiques pouvant atteindre des tailles de plusieurs dizaines de giga-octets. Ces tailles de données nous ont imposées de développer un algorithme parallèle d'extraction d'isosurfaces simplifiées. Le volume est d'abord récursivement découpé pour former une structure hiérarchique de blocs voisins. Des isosurfaces partielles sont extraites de ces blocs par des processeurs indépendants exécutant une version étendue de l'algorithme tandem. Ainsi, les noeuds de calcul extraient, simplifient, s'échangent et assemblent les morceaux de surfaces ainsi obtenues jusqu'à l'obtention d'une isosurface simplifiée globale. Cette dernière est organisée et stockée par construction en un flux de composantes connexes qui permettra une interaction ultérieure de haut niveau.

Systématiser: tel est le leitmotiv des résultats de cette thèse portant sur trois domaines d'étude en vision et en géométrie algorithmique. Dans le premier, nous étendons toute la machinerie du modèle sténopé des appareils photos classiques à un ensemble d'appareils photo (deux fentes, à balayage, oblique, une fente) jusqu'à présent étudiés séparément suivant différentes approches. Dans le deuxième, nous généralisons avec peu d'effort aux convexes de $\R^3$ l'étude des épinglages de droites ou de boules, menée différemment selon la nature des objets considérés. Dans le troisième, nous tentons de dégager une approche systématique pour élaborer des stratégies d'évaluation polynomiale de prédicats géométriques, les méthodes actuelles étant bien souvent spécifiques à chaque prédicat étudié. De tels objectifs ne peuvent être atteints sans un certain investissement mathématique dans l'étude des congruences linéaires de droites, des propriétés différentielles des ensembles de tangentes à des convexes et de la théorie des invariants algébriques, respectivement. Ces outils ou leurs utilisations reposent sur la géométrie des droites de $\p^3(\R)$, construite dans la seconde moitié du XIX\ieme{} siècle mais pas complètement assimilée en géométrie algorithmique et dont nous proposons une synthèse adaptée aux besoins de la communauté.