In these theses are pepresented the Voronoi diagram and Network Voronoi diagram. The shortest path Dijkstra’s algorithm was modified in this way that calculates shortest paths from several Voronoi generators at the same time. The first result - partition of the nodes of the network. The seond result - arcs of the network are attributed to the generators, considering especially their direction and asymmetric costs. Applications allow compare Network Voronoi diagrams to Voronoi diagrams. For this puspose we modified Fortune algorithm. We made particular product for Taxi depot. The user can make his own implementation.

In this work Voronoi diagrams which are drawn by the cellular automaton are discussed. The square and hexagon cellular automata were created and used for drawing Voronoi diagrams. As a result of using the created programs Voronoi diagrams, which are obtained in case of two and more dots, are observed. The following results of the research were achieved: § Voronoi diagram can be obtained by the cellular automaton. § Voronoi diagrams, which were obtained, are not precise due to different speed of movement in different directions. § In square - cell case the obtained diagrams depend on the chosen situation of the neighbors. § In hexagon - cell case the obtained Voronoi diagrams are more but not completely precise. The mathematic calculations are not being made while creating Voronoi diagrams by the cellular automaton.. The diagrams are obtained in short period of time. It is possible to watch the process of the diagram creation. A lot of computer's operation time is lost not during the calculation but for re-drawing the obtained image. This is the reason why it is necessary to optimize the image creating algorithm.

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

This research is motivated by an issue frequently encountered in water quality monitoring and ecological assessment. One concern for researchers and watershed resource managers is how the biological community in a watershed is affected by human activities. The conventional single model approach based on regression and logistic regression usually fails to adequately model the relationship between biological responses and environmental stressors since the study samples are collected over a large spatial region and the response-stressor relationships are usually weak in this situation. In this dissertation, we propose two alternative modeling approaches to partition the whole region of study into disjoint subregions and model the response-stressor relationships within subregions simultaneously. In our examples, these modeling approaches found stronger relationships within subregions and should help the resource managers improve impairment assessment and decision making. The first approach is an adjusted Bayesian classification and regression tree (ABCART). It is based on the Bayesian classification and regression tree approach (BCART) and is modified to accommodate spatial partitions in ecological studies. The second approach is a Voronoi diagram based partition approach. This approach uses the Voronoi diagram technique to randomly partition the whole region into subregions with predetermined minimum sample size. The optimal partition/cluster is selected by Monte Carlo simulation. We propose several model selection criteria for optimal partitioning and modeling according to the nature of the study and extend it to multivariate analysis to find the underlying structure of response-stressor relationships. We also propose a multivariate hotspot detection approach (MHDM) to find the region where the response-stressor relationship is the strongest according to an R-square-like criterion. Several sets of ecological data are studied in this dissertation to illustrate the implementation of the above partition modeling approaches. The findings from these studies are consistent with other studies. / Ph. D.

Mobile robots are increasingly being used to perform tasks in unknown environments. The potential of robots to undertake such tasks lies in their ability to intelligently and efficiently locate and interact with objects in their environment. My research focuses on developing algorithms to plan paths for mobile robots in a partially known environment observed by an overhead camera. The environment consists of dynamic obstacles and targets. A new methodology, Extrapolated Artificial Potential Field, is proposed for real time robot path planning. An algorithm for probabilistic collision detection and avoidance is used to enhance the planner. The aim of the robot is to select avoidance maneuvers to avoid the dynamic obstacles. The navigation of a mobile robot in a real-world dynamic environment is a complex and daunting task. Consider the case of a mobile robot working in an office environment. It has to avoid the static obstacles such as desks, chairs and cupboards and it also has to consider dynamic obstacles such as humans. In the presence of dynamic obstacles, the robot has to predict the motion of the obstacles. Humans inherently have an intuitive motion prediction scheme when planning a path in a crowded environment. A technique has been developed which predicts the possible future positions of obstacles. This technique coupled with the generalized Voronoi diagram enables the robot to safely navigate in a given environment.

This thesis provides strategies for multiple vehicles to explore unknown environments in a cooperative and systematic manner. These strategies are called Simultaneous Cooperative Exploration and Networking (SCENT) strategies. As the basis for development of SCENT strategies, we first tackle the motion control and planning for one vehicle with range sensors. In particular, we develop the curve-tracking controllers for autonomous vehicles with rigidly mounted range sensors, and a provably complete exploration strategy is proposed so that one vehicle with range sensors builds a topological map of an environment. The SCENT algorithms introduced in this thesis extend the exploration strategy for one vehicle to multiple vehicles. The enabling idea of the SCENT algorithms is to construct a topological map of the environment, which is considered completely explored if the map corresponds to a complete Voronoi diagram of the environment. To achieve this, each vehicle explores its local area by incrementally expanding the already visited areas of the environment. At the same time, every vehicle deploys communication devices at selected locations and, as a result, a communication network is created concurrently with a topological map. This additional network allows the vehicles to share information in a distributed manner resulting in an efficient exploration of the workspace. The efficiency of the proposed SCENT algorithms is verified through theoretical investigations as well as experiments using mobile robots. Moreover, the resulting networks and the topological maps are used to solve coordinated multi-robot tasks, such as capturing intruders.

This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.

Several examples of nearly optimal transport networks can be found in nature. These networks effectively distribute and drain fluids throughout a medium. Evidence suggests that blood vessels of the circulatory system, airways in the lungs and veins of leaf venations are examples of networks that have evolved to become effective in their tasks while simultaneously being energy efficient. Hence, it does not come as a surprise that recent performance improvements of modern power generating devices occur due to the use of nature-inspired channel architectures. Guided by this observations, in this work, we investigate the application of visually realistic computer-generated leaf venation patterns to a type of photovoltaic device. We solve the flow through the device problem using Computational Fluid Dynamics (CFD) tools. Moreover, we attempt to develop experimentals models. Ultimately, we seek to single out the network properties that affect their performance. / Diversos exemplos de redes de transporte quase ótimas podem ser encontradas na natureza. Essas redes distribuem e coletam fluidos através de um meio. Evidências sugerem que os vasos sanguíneos do sistema circulatório, as vias respiratórias nos pulmões e as veias das venações em folhas são exemplares de redes que evoluiram para se tornarem efetivas em suas tarefas sendo, ao mesmo tempo, eficientes energeticamente. Dessa forma, não chega a ser surpreendente que recentes melhorias de performance em dispositivos de geração de energia modernos ocorrem devido ao uso de arquiteturas de canais inspiradas na natureza. Guiados por estas observações, nesse trabalho, investigamos a aplicação de padrões de venações verossímeis geradas por computador em um tipo de dispositivo fotovoltaico. Resolvemos o problema de escoamento através do dispositivo usando ferramentas de Dinâmica de Fluidos Computacional (CFD). Além disso, procuramos desenvolver modelos experimentais. Em última instância, estamos em busca das propriedades da rede que afetam sua performance.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho apresenta um estudo teórico e numérico sobre os erros que ocorrem nos cálculos de gradientes em malhas não estruturadas constituídas pelo diagrama de Voronoi, malhas estas, formadas também pela triangulação de Delaunay. As malhas adotadas, no trabalho, foram as malhas cartesianas e as malhas triangulares, esta última é gerada pela divisão de um quadrado em dois ou quatro triângulos iguais. Para tal análise, adotamos a escolha de três metodologias distintas para o cálculo dos gradientes: método de Green Gauss, método do Mínimo Resíduo Quadrático e método da Média do Gradiente Projetado Corrigido. O texto se baseia em dois enfoques principais: mostrar que as equações de erros dadas pelos gradientes podem ser semelhantes, porém com sinais opostos, para pontos de cálculos em volumes vizinhos e que a ordem do erro das equações analíticas pode ser melhorada em malhas uniformes quando comparada as não uniformes, nos casos unidimensionais, e quando analisada na face de tais volumes vizinhos nos casos bidimensionais. / This work presents a theoretical and numerical study on the errors that occur in the calculation of gradients on unstructured meshes Voronoi type, these meshes, also formed by Delaunay triangulation. The meshes adopted in the work were cartesian and triangular meshes, the latter is formed by dividing a square in two or four equal triangles. For this analysis, we adopt the choice of three different methodologies for the calculation of gradients: Green Gauss method, weighted least-squares method and mean value of the projected gradients method. The text is based on two main approaches: to show that the equations of errors given by the gradients may be similar, but with opposite signs, for calculation point in opposite volumes. And show that the order of the error of the analytical equations can be improved in uniform mesh when compared to not uniform, the one-dimensional case, and when viewed from the opposite face of such volumes for the two-dimensional case.

[pt] Este trabalho apresenta um método para extração de malhas poligonais adaptativas em multi-resolução, a partir de objetos volumétricos. As principais aplicações da extração de malhas estão ligadas à área médica, dinâmica de fluidos, geociências, meteorologia, dentre outras. Nestas áreas os dados podem ser representados como objetos volumétricos. Nos dados volumétricos as informações estão representadas implicitamente, o que dificulta o processamento direto dos objetos que se encontram representados dentro do volume. A extração da malha visa obter uma representação explícita dos objetos, de modo a viabilizar o processamento dos mesmos. O método apresentado na tese procura extrair a malha a partir de processos de Simplicação e Refinamento. Durante a simplificação é extraída uma representação super amostrada do objeto (na mesma resolução do volume inicial), a qual é simplificada de modo a se obter uma malha base ou malha grossa, em baixa resolução, porém contendo a topologia correta do objeto. A etapa de refinamento utiliza a transformada de distâ ncia para obter uma representação da malha em multi-resolução, ou seja, a cada instante é obtida uma malha de maior resolução que vai se adaptando progressivamente à geometria do objeto. A malha final apresenta uma série de propriedades importantes, como boa razão de aspecto dos triângulos, converge para a superfície do objeto, pode ser aplicada tanto a objetos com borda quanto a objetos sem borda, pode ser aplicada tanto a superfície conexas quanto a não conexas, dentre outras. / [en] This work presents a method for extracting multiresolution adaptive polygonal meshes, from volumetric objects. Main aplications of this work are related to medical area, fluid dynamics, geosciences, metheorology and others. In these areas data may be represented as volumetric objects. Volumetric datasets are implicit representations of objects, so it s very dificult to apply directly any process to these objects. Mesh extraction obtains an explicit representation of the objetc, such that it s easier to process directly the objects. The presented method extracts the mesh from two main processes: Simplification and Refinement. The simplification step extracts a supersampled representation of the object (in the same volume resolution), and simplifies it in such a way to obtain a base mesh (or coarse mesh), in a low resolution, but containing the correct topology of the object. Refinement step uses the distance transform to obtain a multiresolution representation of the mesh, it means that at each instant it s obtained an adaptive higher resolution mesh. The final mesh presents a set of important properties, like good triangle aspect ratio, convergency to the object surface, may be applied as to objects with boundary and as to objects with multiple connected components, among others properties.