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.

Representação da área de responsabilidade de jogadores de futebol através do Diagrama de Voronoi

Universidade Estadual de Campinas . Faculdade de Educação Física

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.

Specialized care for people with AIDS in the state of Ceara, Brazil

OBJECTIVE To analyze if the distribution of specialized care services for HIV/AIDS is associated with AIDS rates. METHODS Ecological study, for which the distribution of 10 specialized care services in the Ceara state, Northeastern Brazil, was obtained, and the mean rates of the disease were estimated per mesoregion. We evaluated 7,896 individuals who had been diagnosed with AIDS, were aged 13 years or older, lived in Ceara, and had been informed of their condition between 2001 and 2011. Maps were constructed to verify the relationship between the distribution of AIDS cases and institutionalized support networks in the 2001-2006 and 2007-2011 periods. BoxMap and LisaMap were used for data analysis. The Voronoi diagram was applied for the distribution of the studied services. RESULTS Specialized care services concentrated in AIDS clusters in the metropolitan area. The Noroeste Cearense and west of the Sertoes Cearenses had high AIDS rates, but a low number of specialized care services over time. Two of these services were implemented where clusters of the disease exist in the second period. The application of the Voronoi diagram showed that the specialized care services located outside the metropolitan area covered a large territory. We identified one polygon that had no services. CONCLUSIONS The scenario of AIDS cases spread away from major urban areas demands the creation of social support services in areas other than the capital and the metropolitan area of the state; this can reduce access barriers to these institutions. It is necessary to create specialized care services for HIV/AIDS in the Noroeste Cearense and north of Jaguaribe.

Early white matter alterations in men predisposed to FXTAS revealed by MT imaging.

Introduction: The Fragile X - associated Tremor Ataxia Syndrome (FXTAS) is a recently described, and under-diagnosed, late onset (≈ 60y) neurodegenerative disorder affecting male carriers of a premutation in the Fragile X Mental Retardation 1 (FMR1) gene. The premutation is an CGG (Cytosine-Guanine-Guanine) expansion (55 to 200 CGG repeats) in the proximal region of the FMR1 gene. Patients with FXTAS primarily present with cerebellar ataxia and intention tremor. Neuroradiological features of FXTAS include prominent white matter disease in the periventricular, subcortical, middle cerebellar peduncles and deep white matter of the cerebellum on T2-weighted or FLAIR MR imaging (Jacquemmont 2007, Loesch 2007, Brunberg 2002, Cohen 2006). We hypothesize that a significant white matter alteration is present in younger individuals many years prior to clinical symptoms and/or the presence of visible lesions on conventional MR sequences and might be detectable by magnetization transfer (MT) imaging. Methods: Eleven asymptomatic premutation carriers (mean age = 55 years) and seven intra-familial controls participated to the study. A standardized neurological examination was performed on all participants and a neuropsychological evaluation was carried out before MR scanning performed on a 3T Siemens Trio. The protocol included a sagittal T1-weighted 3D gradient-echo sequence (MPRAGE, 160 slices, 1 mm^3 isotropic voxels) and a gradient-echo MTI (FA 30, TE 15, matrix size 256*256, pixel size 1*1 mm, 36 slices (thickness 2mm), MT pulse duration 7.68 ms, FA 500, frequency offset 1.5 kHz). MTI was performed by acquiring consecutively two set of images; first with and then without the MT saturation pulse. MT images were coregistered to the T1 acquisition. The MTR for every intracranial voxel was calculated as follows: MTR = (M0 - MS)/M0*100%, creating a MTR map for each subject. As first analysis, the whole white matter (WM) was used to mask the MTR image in order to create an histogram of the MTR distribution in the whole tissue class over the two groups examined. Then, for each subject, we performed a segmentation and parcellation of the brain by means of Freesurfer software, starting from the high resolution T1-weighted anatomical acquisition. Cortical parcellations was used to assign a label to the underlying white matter by the construction of a Voronoi diagram in the WM voxels of the MR volume based on distance to the nearest cortical parcellation label. This procedure allowed us to subdivide the cerebral WM in 78 ROIs according to the cortical parcellation (see example in Fig 1). The cerebellum, by the same procedure, was subdivided in 5 ROIs (2 per each hemisphere and one corresponding to the brainstem). For each subject, we calculated the mean value of MTR within each ROI and averaged over controls and patients. Significant differences between the two groups were tested using a two sample T-test (p<0.01). Results: Neurological examination showed that no patient met the clinical criteria of Fragile X Tremor and Ataxia Syndrome yet. Nonetheless, premutation carriers showed some subtle neurological signs of the disorder. In fact, premutation carriers showed a significant increase of tremor (CRST, T-test p=0.007) and increase of ataxia (ICARS, p=0.004) when compared to controls. The neuropsychological evaluation was normal in both groups. To obtain general characterizations of myelination for each subject and premutation carriers, we first computed the distribution of MTR values across the total white matter volume and averaged for each group. We tested the equality of the two distributions with the non parametric Kolmogorov-Smirnov test and we rejected the null-hypothesis at a p=0.03 (fig. 2). As expected, when comparing the asymptomatic permutation carriers with control subjects, the peak value and peak position of the MTR values within the whole WM were decreased and the width of the distribution curve was increased (p<0.01). These three changes point to an alteration of the global myelin status of the premutation carriers. Subsequently, to analyze the regional myelination and white matter integrity of the same group, we performed a ROI analysis of MTR data. The ROI-based analysis showed a decrease of mean MTR value in premutation carriers compared to controls in bilateral orbito-frontal and inferior frontal WM, entorhinal and cingulum regions and cerebellum (Fig 3). The detection of these differences in these regions failed with other conventional MR techniques. Conclusions: These preliminary data confirm that in premutation carriers, there are indeed alterations in "normal appearing white matter" (NAWM) and these alterations are visible with the MT technique. These results indicate that MT imaging may be a relevant approach to detect both global and local alterations within NAWM in "asymptomatic" carriers of premutations in the Fragile X Mental Retardation 1 (FMR1) gene. The sensitivity of MT in the detection of these alterations might point towards a specific physiopathological mechanism linked to an underlying myelin disorder. ROI-based analyses show that the frontal, parahippocampal and cerebellar regions are already significantly affected before the onset of symptoms. A larger sample will allow us to determine the minimum CGG expansion and age associated with these subclinical white matter alterations.

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.

Phase diagram of a model for a binary mixture of nematic molecules on a Bethe lattice

We investigate the phase diagram of a discrete version of the Maier-Saupe model with the inclusion of additional degrees of freedom to mimic a distribution of rodlike and disklike molecules. Solutions of this problem on a Bethe lattice come from the analysis of the fixed points of a set of nonlinear recursion relations. Besides the fixed points associated with isotropic and uniaxial nematic structures, there is also a fixed point associated with a biaxial nematic structure. Due to the existence of large overlaps of the stability regions, we resorted to a scheme to calculate the free energy of these structures deep in the interior of a large Cayley tree. Both thermodynamic and dynamic-stability analyses rule out the presence of a biaxial phase, in qualitative agreement with previous mean-field results.