Connecting red cells in a bichromatic Voronoi diagram

Let S be a set of n + m sites, of which n are red and have weight wR, and m are blue and weigh wB. The objective of this paper is to calculate the minimum value of wR such that the union of the red Voronoi cells in the weighted Voronoi diagram of S is a connected set. The problem is solved for the multiplicatively-weighted Voronoi diagram in O((n+m)^2 log(nm)) time and for the additively-weighted Voronoi diagram in O(nmlog(nm)) time.

Estimativa de erros no cálculo de gradientes em malhas de Voronoi

O presente trabalho propõe analisar metodologias para o cálculo do gradiente em malhas não-estruturadas do tipo Voronoi que são utilizadas no método de Volumes Finitos. Quatro metodologias para o cálculo do gradiente são testadas e comparadas com soluções analíticas. As técnicas utilizadas são: Método do Balanço de Forças, Método do Mínimo Resíduo Quadrático, Método da Média dos Gradientes Projetos e Método da Média dos Gradientes Projetados Corrigidos. Uma análise por série de Taylor também foi feita, e as equações analíticas comparadas com resultados numéricos. Os testes são realizados em malhas cartesianas e malhas triangulares, que em um trabalho anterior apresentaram alguns resultados inconsistentes. A influência do ponto gerador e do ângulo de rotação é analisada. É verificado que a posição do ponto gerador e a metodologia utilizada em cada malha influencia no cálculo do gradiente. Dependendo da malha e da metodologia utilizada, as equações analíticas indicaram que existem erros associados, que prejudicam o cálculo do gradiente.

Classificação fuzzy de vertentes por krigagem e TPS com agregação de regiões via diagrama de Voronoi

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Zone design of specific sizes using adaptive additively weighted voronoi diagrams

Territory or zone design processes entail partitioning a geographic space, organized as a set of areal units, into different regions or zones according to a specific set of criteria that are dependent on the application context. In most cases, the aim is to create zones of approximately equal sizes (zones with equal numbers of inhabitants, same average sales, etc.). However, some of the new applications that have emerged, particularly in the context of sustainable development policies, are aimed at defining zones of a predetermined, though not necessarily similar, size. In addition, the zones should be built around a given set of seeds. This type of partitioning has not been sufficiently researched; therefore, there are no known approaches for automated zone delimitation. This study proposes a new method based on a discrete version of the adaptive additively weighted Voronoi diagram that makes it possible to partition a two-dimensional space into zones of specific sizes, taking both the position and the weight of each seed into account. The method consists of repeatedly solving a traditional additively weighted Voronoi diagram, so that each seed?s weight is updated at every iteration. The zones are geographically connected using a metric based on the shortest path. Tests conducted on the extensive farming system of three municipalities in Castile-La Mancha (Spain) have established that the proposed heuristic procedure is valid for solving this type of partitioning problem. Nevertheless, these tests confirmed that the given seed position determines the spatial configuration the method must solve and this may have a great impact on the resulting partition.

Voronoi cells via linear inequality systems

The theory and methods of linear algebra are a useful alternative to those of convex geometry in the framework of Voronoi cells and diagrams, which constitute basic tools of computational geometry. As shown by Voigt and Weis in 2010, the Voronoi cells of a given set of sites T, which provide a tesselation of the space called Voronoi diagram when T is finite, are solution sets of linear inequality systems indexed by T. This paper exploits systematically this fact in order to obtain geometrical information on Voronoi cells from sets associated with T (convex and conical hulls, tangent cones and the characteristic cones of their linear representations). The particular cases of T being a curve, a closed convex set and a discrete set are analyzed in detail. We also include conclusions on Voronoi diagrams of arbitrary sets.

乡镇级人口统计数据空间化研究

Population data which collected and saved according to administrative region is a kind of statistical data. As a traditional method of spatial data expression, average distribution in every administrative region brings population data on a low spatial and temporal precision. Now, an accurate population data with high spatial resolution is becoming more and more important in regional planning, environment protection, policy making and rural-urban development. Spatial distribution of population data is becoming more important in GIS study area. In this article, the author reviewed the progress of research on spatial distribution of population. Under the support of GIS, correlative geographical theories and Grid data model, Remote Sensing data, terrain data, traffic data, river data, resident data, and social economic statistic were applied to calculate the spatial distribution of population in Fujian province, which includes following parts: (1) Simulating of boundary at township level. Based on access cost index, land use data, traffic data, river data, DEM, and correlative social economic statistic data, the access cost surface in study area was constructed. Supported by the lowest cost path query and weighted Voronoi diagram, DVT model (Demarcation of Villages and Towns) was established to simulate the boundary at township level in Fujian province. (2) Modeling of population spatial distribution. Based on the knowledge in geography, seven impact factors, such as land use, altitude, slope, residential area, railway, road, and river were chosen as the parameters in this study. Under the support of GIS, the relations of population distribution to these impact factors were analyzed quantificationally, and the coefficients of population density on pixel scale were calculated. Last, the model of population spatial distribution at township level was established through multiplicative fusion of population density coefficients and simulated boundary of towns. (3) Error test and analysis of population spatial distribution base on modeling. The author not only analyzed the numerical character of modeling error, but also its spatial distribution. The reasons of error were discussed.

Motion Planning with Six Degrees of Freedom

The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. In robotics we are interested in the automatic synthesis of robot motions, given high-level specifications of tasks and geometric models of the robot and obstacles. The Mover's problem is to find a continuous, collision-free path for a moving object through an environment containing obstacles. We present an implemented algorithm for the classical formulation of the three-dimensional Mover's problem: given an arbitrary rigid polyhedral moving object P with three translational and three rotational degrees of freedom, find a continuous, collision-free path taking P from some initial configuration to a desired goal configuration. This thesis describes the first known implementation of a complete algorithm (at a given resolution) for the full six degree of freedom Movers' problem. The algorithm transforms the six degree of freedom planning problem into a point navigation problem in a six-dimensional configuration space (called C-Space). The C-Space obstacles, which characterize the physically unachievable configurations, are directly represented by six-dimensional manifolds whose boundaries are five dimensional C-surfaces. By characterizing these surfaces and their intersections, collision-free paths may be found by the closure of three operators which (i) slide along 5-dimensional intersections of level C-Space obstacles; (ii) slide along 1- to 4-dimensional intersections of level C-surfaces; and (iii) jump between 6 dimensional obstacles. Implementing the point navigation operators requires solving fundamental representational and algorithmic questions: we will derive new structural properties of the C-Space constraints and shoe how to construct and represent C-Surfaces and their intersection manifolds. A definition and new theoretical results are presented for a six-dimensional C-Space extension of the generalized Voronoi diagram, called the C-Voronoi diagram, whose structure we relate to the C-surface intersection manifolds. The representations and algorithms we develop impact many geometric planning problems, and extend to Cartesian manipulators with six degrees of freedom.

Limited range coverage problems

Tal como o título indica, esta tese estuda problemas de cobertura com alcance limitado. Dado um conjunto de antenas (ou qualquer outro dispositivo sem fios capaz de receber ou transmitir sinais), o objectivo deste trabalho é calcular o alcance mínimo das antenas de modo a que estas cubram completamente um caminho entre dois pontos numa região. Um caminho que apresente estas características é um itinerário seguro. A definição de cobertura é variável e depende da aplicação a que se destina. No caso de situações críticas como o controlo de fogos ou cenários militares, a definição de cobertura recorre à utilização de mais do que uma antena para aumentar a eficácia deste tipo de vigilância. No entanto, o alcance das antenas deverá ser minimizado de modo a manter a vigilância activa o maior tempo possível. Consequentemente, esta tese está centrada na resolução deste problema de optimização e na obtenção de uma solução particular para cada caso. Embora este problema de optimização tenha sido investigado como um problema de cobertura, é possível estabelecer um paralelismo entre problemas de cobertura e problemas de iluminação e vigilância, que são habitualmente designados como problemas da Galeria de Arte. Para converter um problema de cobertura num de iluminação basta considerar um conjunto de luzes em vez de um conjunto de antenas e submetê-lo a restrições idênticas. O principal tema do conjunto de problemas da Galeria de Arte abordado nesta tese é a 1-boa iluminação. Diz-se que um objecto está 1-bem iluminado por um conjunto de luzes se o invólucro convexo destas contém o objecto, tornando assim este conceito num tipo de iluminação de qualidade. O objectivo desta parte do trabalho é então minimizar o alcance das luzes de modo a manter uma iluminação de qualidade. São também apresentadas duas variantes da 1-boa iluminação: a iluminação ortogonal e a boa !-iluminação. Esta última tem aplicações em problemas de profundidade e visualização de dados, temas que são frequentemente abordados em estatística. A resolução destes problemas usando o diagrama de Voronoi Envolvente (uma variante do diagrama de Voronoi adaptada a problemas de boa iluminação) é também proposta nesta tese.

Face Recognition using Probabilistic Neural Networks

In this paper we address the problem of face detection and recognition of grey scale frontal view images. We propose a face recognition system based on probabilistic neural networks (PNN) architecture. The system is implemented using voronoi/ delaunay tessellations and template matching. Images are segmented successfully into homogeneous regions by virtue of voronoi diagram properties. Face verification is achieved using matching scores computed by correlating edge gradients of reference images. The advantage of classification using PNN models is its short training time. The correlation based template matching guarantees good classification results

Face Recognition using Probabilistic Neural Networks

n this paper we address the problem of face detection and recognition of grey scale frontal view images. We propose a face recognition system based on probabilistic neural networks (PNN) architecture. The system is implemented using voronoi/ delaunay tessellations and template matching. Images are segmented successfully into homogeneous regions by virtue of voronoi diagram properties. Face verification is achieved using matching scores computed by correlating edge gradients of reference images. The advantage of classification using PNN models is its short training time. The correlation based template matching guarantees good classification results.

Visibility and proximity on triangulated surfaces

En aquesta tesi es solucionen problemes de visibilitat i proximitat sobre superfícies triangulades considerant elements generalitzats. Com a elements generalitzats considerem: punts, segments, poligonals i polígons. Les estrategies que proposem utilitzen algoritmes de geometria computacional i hardware gràfic. Comencem tractant els problemes de visibilitat sobre models de terrenys triangulats considerant un conjunt d'elements de visió generalitzats. Es presenten dos mètodes per obtenir, de forma aproximada, mapes de multi-visibilitat. Un mapa de multi-visibilitat és la subdivisió del domini del terreny que codifica la visibilitat d'acord amb diferents criteris. El primer mètode, de difícil implementació, utilitza informació de visibilitat exacte per reconstruir de forma aproximada el mapa de multi-visibilitat. El segon, que va acompanyat de resultats d'implementació, obté informació de visibilitat aproximada per calcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Com a aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntes sobre la multi-visibilitat d'un punt o d'una regió. A continuació tractem els problemes de proximitat sobre superfícies polièdriques triangulades considerant seus generalitzades. Es presenten dos mètodes, amb resultats d'implementació, per calcular distàncies des de seus generalitzades sobre superfícies polièdriques on hi poden haver obstacles generalitzats. El primer mètode calcula, de forma exacte, les distàncies definides pels camins més curts des de les seus als punts del poliedre. El segon mètode calcula, de forma aproximada, distàncies considerant els camins més curts sobre superfícies polièdriques amb pesos. Com a aplicacions, es calculen diagrames de Voronoi d'ordre k, i es resolen, de forma aproximada, alguns problemes de localització de serveis. També es proporciona un estudi teòric sobre la complexitat dels diagrames de Voronoi d'ordre k d'un conjunt de seus generalitzades en un poliedre sense pesos.

Surface coverage in wireless sensor networks based on delaunay tetrahedralization

In this work is presented a new method for sensor deployment on 3D surfaces. The method was structured on different steps. The first one aimed discretizes the relief of interest with Delaunay algorithm. The tetrahedra and relative values (spatial coordinates of each vertex and faces) were input to construction of 3D Voronoi diagram. Each circumcenter was calculated as a candidate position for a sensor node: the corresponding circular coverage area was calculated based on a radius r. The r value can be adjusted to simulate different kinds of sensors. The Dijkstra algorithm and a selection method were applied to eliminate candidate positions with overlapped coverage areas or beyond of surface of interest. Performance evaluations measures were defined using coverage area and communication as criteria. The results were relevant, once the mean coverage rate achieved on three different surfaces were among 91% and 100%.

Zonificación del espacio por agrupación de unidades superficiales. Aplicación a la gestión de sistemas extensivos del tipo cereal-ovino

RESUMEN Los procesos de diseño de zonas o diseño del territorio implican la partición de un espacio geográfico, organizado en un conjunto de unidades de área, en diferentes regiones o zonas según un conjunto especifico de criterios que varían en función del campo de aplicación. En la mayoría de los casos, el objetivo fundamental consiste en crear zonas de tamaño aproximadamente igual respecto a uno o varios atributos de medida -de carácter cuantitativo- (zonas con igual número de habitantes, igual promedio de ventas...). Sin embargo, están apareciendo nuevas aplicaciones, algunas en el contexto de las políticas de desarrollo sostenible, cuya finalidad es la definición de regiones con un tamaño predeterminado, no necesariamente similar. Además, en estos casos las zonas han de formarse en torno a un conjunto específico de posiciones, semillas o generadores. Este tipo de particiones no han sido lo suficientemente investigadas, de manera que no se conocen modelos de solución para la delimitación automática de las zonas. En esta tesis se ha diseñado un nuevo método basado en una versión discreta del diagrama de Voronoi con peso aditivo adaptativo (DVPAA), que permite la partición de un espacio bidimensional en zonas de un tamaño específico, considerando tanto la posición como el peso de cada uno de los generadores. El método consiste en resolver repetidamente un tradicional diagrama de Voronoi con peso aditivo, de forma que los pesos de cada generador se actualizan en cada iteración. En el proceso de cálculo de distancias se usa una métrica basada en el camino más corto, lo que garantiza que la partición obtenida esté formada por un conjunto de zonas conexas. La heurística diseñada se integra en una aplicación prototipo, desarrollada en un entorno SIG (Sistemas de Información Geográfica), que permite el trazado automático de zonas según los criterios anteriormente expuestos. Para analizar la viabilidad del método se ha utilizado como caso de estudio la gestión de los recursos pastorales para la ganadería extensiva en tres municipios de Castilla-La Mancha. Las pruebas realizadas ponen de manifiesto que la heurística diseñada, adaptada a los criterios que se plantean en el contexto de la gestión de sistemas extensivos agropecuarios, es válida para resolver este tipo de problemas de partición. El método propuesto se caracteriza por su eficacia en el tratamiento de un gran número de unidades superficiales en formato vectorial, generando soluciones que convergen con relativa rapidez y verifican los criterios establecidos. En el caso estudiado, aunque la posición prefijada de los generadores reduce considerablemente la complejidad del problema, existen algunas configuraciones espaciales de estos elementos para las que el algoritmo no encuentra una solución satisfactoria, poniéndose de manifiesto una de las limitaciones de este modelo. Tal y como se ha podido comprobar, la localización de los generadores puede tener un considerable impacto en la zonificación resultante, por lo que, de acuerdo con Kalcsics et al. (2005), una selección "inadecuada" difícilmente puede generar regiones válidas que verifiquen los criterios establecidos. ABSTRACT Tenitory or zone design processes entail partitioning a geographic space, organized as a set of basic areal units, into different regions or zones according to a specific set of entena that are dependent on the application context. In most cases the aim is to create zones that have approximately equal sizes with respect to one or several measure attributes (zones with equal numbers of inhabitants, same average sales, etc). However, some of the new applications that have emerged, particularly in the context of sustainable development policies, are aimed at defining zones of a predetermined, though not necessarily similar, size. In addition, the zones should be built around a given set of positions, seeds or generators. This type of partitioning has not been sufñciently researched; therefore there are no known approaches for automated zone delimitation. This thesis proposes a new method based on a discrete versión of the Adaptive Additively Weighted Voronoi Diagram (AAWVD) that makes it possible to partition a 2D space into zones of specific sizes, taking both the position and the weight of each (seed) generator into account. The method consists of repeatedly solving a traditional additively weighted Voronoi diagram, so that the weights of each generator are updated at every iteration. The partition s zones are geographically connected nsing a metric based 011 the shortest path. The proposed heuristic lias been included in an application, developed in a GIS environment that allows the automated zone delimitation according to the mentioned criteria. The management of the extensive farming system of three municipalities of Castilla-La Mancha (Spain) has been used as study case to analyze the viability of the method. The tests carried out have established that the proposed method, adapted to the criteria of this application field, is valid for solving this type of partition problem. The applied algorithm is capable of handling a high number of vector areal units, generating solutions that converge in a reasonable CPU time and comply with the imposed constraints. Although the complexity of this problem is greatly reduced when the generator's positions are fixed, in many cases, these positions impose a spatial confignration that the algorithm proposed is unable to solve, thus revealing one of the limitations of this method. It has been shown that the location of the generators has a considerable impact on the final solution, so that, as Kalcsics et al. (2005) observed, an "inadequate" selection can hardly generate valid zones that comply with the established criteria.

Teleonomic entropy: measuring the phase-space of end-directed systems

We introduce a novel way of measuring the entropy of a set of values undergoing changes. Such a measure becomes useful when analyzing the temporal development of an algorithm designed to numerically update a collection of values such as artificial neural network weights undergoing adjustments during learning. We measure the entropy as a function of the phase-space of the values, i.e. their magnitude and velocity of change, using a method based on the abstract measure of entropy introduced by the philosopher Rudolf Carnap. By constructing a time-dynamic two-dimensional Voronoi diagram using Voronoi cell generators with coordinates of value- and value-velocity (change of magnitude), the entropy becomes a function of the cell areas. We term this measure teleonomic entropy since it can be used to describe changes in any end-directed (teleonomic) system. The usefulness of the method is illustrated when comparing the different approaches of two search algorithms, a learning artificial neural network and a population of discovering agents. (C) 2004 Elsevier Inc. All rights reserved.