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

Measuring spatial interaction behavior in team sports using superimposed Voronoi diagrams

In team sports, the spatial distribution of players on the field is determined by the interaction behavior established at both player and team levels. The distribution patterns observed during a game emerge from specific technical and tactical methods adopted by the teams, and from individual, environmental and task constraints that influence players' behaviour. By understanding how specific patterns of spatial interaction are formed, one can characterize the behavior of the respective teams and players. Thus, in the present work we suggest a novel spatial method for describing teams' spatial interaction behaviour, which results from superimposing the Voronoi diagrams of two competing teams. We considered theoretical patterns of spatial distribution in a well-defined scenario (5 vs 4+ GK played in a field of 20x20m) in order to generate reference values of the variables derived from the superimposed Voronoi diagrams (SVD). These variables were tested in a formal application to empirical data collected from 19 Futsal trials with identical playing settings. Results suggest that it is possible to identify a number of characteristics that can be used to describe players' spatial behavior at different levels, namely the defensive methods adopted by the players.

Spatial dynamics of team sports exposed by Voronoi diagrams

Team sports represent complex systems: players interact continuously during a game, and exhibit intricate patterns of interaction, which can be identified and investigated at both individual and collective levels. We used Voronoi diagrams to identify and investigate the spatial dynamics of players' behavior in Futsal. Using this tool, we examined 19 plays of a sub-phase of a Futsal game played in a reduced area (20 m(2)) from which we extracted the trajectories of all players. Results obtained from a comparative analysis of player's Voronoi area (dominant region) and nearest teammate distance revealed different patterns of interaction between attackers and defenders, both at the level of individual players and teams. We found that, compared to defenders, larger dominant regions were associated with attackers. Furthermore, these regions were more variable in size among players from the same team but, at the player level, the attackers' dominant regions were more regular than those associated with each of the defenders. These findings support a formal description of the dynamic spatial interaction of the players, at least during the particular sub-phase of Futsal investigated. The adopted approach may be extended to other team behaviors where the actions taken at any instant in time by each of the involved agents are associated with the space they occupy at that particular time.

Construção e edição de diagramas de Voronoi na esfera

Dissertação para obtenção do Grau de Doutor em Informática

Generalized Higher-Order Voronoi Diagrams on Polyhedral Surfaces

We present an algorithm for computing exact shortest paths, and consequently distances, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex polyhedral surface in which polygonal chain or polygon obstacles are allowed. We also present algorithms for computing discrete Voronoi diagrams of a set of generalized sites (points, segments, polygonal chains or polygons) on a polyhedral surface with obstacles. To obtain the discrete Voronoi diagrams our algorithms, exploiting hardware graphics capabilities, compute shortest path distances defined by the sites

Voronoi, Delaunay, and Block-Structured Mesh Refinement for Solution of the Shallow-Water Equations on the Sphere

Alternative meshes of the sphere and adaptive mesh refinement could be immensely beneficial for weather and climate forecasts, but it is not clear how mesh refinement should be achieved. A finite-volume model that solves the shallow-water equations on any mesh of the surface of the sphere is presented. The accuracy and cost effectiveness of four quasi-uniform meshes of the sphere are compared: a cubed sphere, reduced latitude–longitude, hexagonal–icosahedral, and triangular–icosahedral. On some standard shallow-water tests, the hexagonal–icosahedral mesh performs best and the reduced latitude–longitude mesh performs well only when the flow is aligned with the mesh. The inclusion of a refined mesh over a disc-shaped region is achieved using either gradual Delaunay, gradual Voronoi, or abrupt 2:1 block-structured refinement. These refined regions can actually degrade global accuracy, presumably because of changes in wave dispersion where the mesh is highly nonuniform. However, using gradual refinement to resolve a mountain in an otherwise coarse mesh can improve accuracy for the same cost. The model prognostic variables are height and momentum collocated at cell centers, and (to remove grid-scale oscillations of the A grid) the mass flux between cells is advanced from the old momentum using the momentum equation. Quadratic and upwind biased cubic differencing methods are used as explicit corrections to a fast implicit solution that uses linear differencing.

From symmetry breaking to Poisson Point Process in 2D Voronoi Tessellations: the generic nature of hexagons

We bridge the properties of the regular triangular, square, and hexagonal honeycomb Voronoi tessellations of the plane to the Poisson-Voronoi case, thus analyzing in a common framework symmetry breaking processes and the approach to uniform random distributions of tessellation-generating points. We resort to ensemble simulations of tessellations generated by points whose regular positions are perturbed through a Gaussian noise, whose variance is given by the parameter α2 times the square of the inverse of the average density of points. We analyze the number of sides, the area, and the perimeter of the Voronoi cells. For all valuesα >0, hexagons constitute the most common class of cells, and 2-parameter gamma distributions provide an efficient description of the statistical properties of the analyzed geometrical characteristics. The introduction of noise destroys the triangular and square tessellations, which are structurally unstable, as their topological properties are discontinuous in α = 0. On the contrary, the honeycomb hexagonal tessellation is topologically stable and, experimentally, all Voronoi cells are hexagonal for small but finite noise withα <0.12. For all tessellations and for small values of α, we observe a linear dependence on α of the ensemble mean of the standard deviation of the area and perimeter of the cells. Already for a moderate amount of Gaussian noise (α >0.5), memory of the specific initial unperturbed state is lost, because the statistical properties of the three perturbed regular tessellations are indistinguishable. When α >2, results converge to those of Poisson-Voronoi tessellations. The geometrical properties of n-sided cells change with α until the Poisson- Voronoi limit is reached for α > 2; in this limit the Desch law for perimeters is shown to be not valid and a square root dependence on n is established. This law allows for an easy link to the Lewis law for areas and agrees with exact asymptotic results. Finally, for α >1, the ensemble mean of the cells area and perimeter restricted to the hexagonal cells agree remarkably well with the full ensemble mean; this reinforces the idea that hexagons, beyond their ubiquitous numerical prominence, can be interpreted as typical polygons in 2D Voronoi tessellations.

Symmetry-break in Voronoi tessellations

We analyse in a common framework the properties of the Voronoi tessellations resulting from regular 2D and 3D crystals and those of tessellations generated by Poisson distributions of points, thus joining on symmetry breaking processes and the approach to uniform random distributions of seeds. We perturb crystalline structures in 2D and 3D with a spatial Gaussian noise whose adimensional strength is α and analyse the statistical properties of the cells of the resulting Voronoi tessellations using an ensemble approach. In 2D we consider triangular, square and hexagonal regular lattices, resulting into hexagonal, square and triangular tessellations, respectively. In 3D we consider the simple cubic (SC), body-centred cubic (BCC), and face-centred cubic (FCC) crystals, whose corresponding Voronoi cells are the cube, the truncated octahedron, and the rhombic dodecahedron, respectively. In 2D, for all values α>0, hexagons constitute the most common class of cells. Noise destroys the triangular and square tessellations, which are structurally unstable, as their topological properties are discontinuous in α=0. On the contrary, the honeycomb hexagonal tessellation is topologically stable and, experimentally, all Voronoi cells are hexagonal for small but finite noise with α<0.12. Basically, the same happens in the 3D case, where only the tessellation of the BCC crystal is topologically stable even against noise of small but finite intensity. In both 2D and 3D cases, already for a moderate amount of Gaussian noise (α>0.5), memory of the specific initial unperturbed state is lost, because the statistical properties of the three perturbed regular tessellations are indistinguishable. When α>2, results converge to those of Poisson-Voronoi tessellations. In 2D, while the isoperimetric ratio increases with noise for the perturbed hexagonal tessellation, for the perturbed triangular and square tessellations it is optimised for specific value of noise intensity. The same applies in 3D, where noise degrades the isoperimetric ratio for perturbed FCC and BCC lattices, whereas the opposite holds for perturbed SCC lattices. This allows for formulating a weaker form of the Kelvin conjecture. By analysing jointly the statistical properties of the area and of the volume of the cells, we discover that also the cells shape heavily fluctuates when noise is introduced in the system. In 2D, the geometrical properties of n-sided cells change with α until the Poisson-Voronoi limit is reached for α>2; in this limit the Desch law for perimeters is shown to be not valid and a square root dependence on n is established, which agrees with exact asymptotic results. Anomalous scaling relations are observed between the perimeter and the area in the 2D and between the areas and the volumes of the cells in 3D: except for the hexagonal (2D) and FCC structure (3D), this applies also for infinitesimal noise. In the Poisson-Voronoi limit, the anomalous exponent is about 0.17 in both the 2D and 3D case. A positive anomaly in the scaling indicates that large cells preferentially feature large isoperimetric quotients. As the number of faces is strongly correlated with the sphericity (cells with more faces are bulkier), in 3D it is shown that the anomalous scaling is heavily reduced when we perform power law fits separately on cells with a specific number of faces.

Three-dimensional random Voronoi tessellations: From cubic crystal lattices to Poisson point processes

We perturb the SC, BCC, and FCC crystal structures with a spatial Gaussian noise whose adimensional strength is controlled by the parameter a, and analyze the topological and metrical properties of the resulting Voronoi Tessellations (VT). The topological properties of the VT of the SC and FCC crystals are unstable with respect to the introduction of noise, because the corresponding polyhedra are geometrically degenerate, whereas the tessellation of the BCC crystal is topologically stable even against noise of small but finite intensity. For weak noise, the mean area of the perturbed BCC and FCC crystals VT increases quadratically with a. In the case of perturbed SCC crystals, there is an optimal amount of noise that minimizes the mean area of the cells. Already for a moderate noise (a>0.5), the properties of the three perturbed VT are indistinguishable, and for intense noise (a>2), results converge to the Poisson-VT limit. Notably, 2-parameter gamma distributions are an excellent model for the empirical of of all considered properties. The VT of the perturbed BCC and FCC structures are local maxima for the isoperimetric quotient, which measures the degre of sphericity of the cells, among space filling VT. In the BCC case, this suggests a weaker form of the recentluy disproved Kelvin conjecture. Due to the fluctuations of the shape of the cells, anomalous scalings with exponents >3/2 is observed between the area and the volumes of the cells, and, except for the FCC case, also for a->0. In the Poisson-VT limit, the exponent is about 1.67. As the number of faces is positively correlated with the sphericity of the cells, the anomalous scaling is heavily reduced when we perform powerlaw fits separately on cells with a specific number of faces.

THE VORONOI TESSELLATION CLUSTER FINDER IN 2+1 DIMENSIONS

We present a detailed description of the Voronoi Tessellation (VT) cluster finder algorithm in 2+1 dimensions, which improves on past implementations of this technique. The need for cluster finder algorithms able to produce reliable cluster catalogs up to redshift 1 or beyond and down to 10(13.5) solar masses is paramount especially in light of upcoming surveys aiming at cosmological constraints from galaxy cluster number counts. We build the VT in photometric redshift shells and use the two-point correlation function of the galaxies in the field to both determine the density threshold for detection of cluster candidates and to establish their significance. This allows us to detect clusters in a self-consistent way without any assumptions about their astrophysical properties. We apply the VT to mock catalogs which extend to redshift 1.4 reproducing the ACDM cosmology and the clustering properties observed in the Sloan Digital Sky Survey data. An objective estimate of the cluster selection function in terms of the completeness and purity as a function of mass and redshift is as important as having a reliable cluster finder. We measure these quantities by matching the VT cluster catalog with the mock truth table. We show that the VT can produce a cluster catalog with completeness and purity > 80% for the redshift range up to similar to 1 and mass range down to similar to 10(13.5) solar masses.

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)

Study of cerebral gene expression densities using Voronoi analysis

As the available public cerebral gene expression image data increasingly grows, the demand for automated methods to analyze such large amount of data also increases. An important study that can be carried out on these data is related to the spatial relationship between gene expressions. Similar spatial density distribution of expression between genes may indicate they are functionally correlated, thus the identification of these similarities is useful in suggesting directions of investigation to discover gene interactions and their correlated functions. In this paper, we describe the use of a high-throughput methodology based on Voronoi diagrams to automatically analyze and search for possible local spatial density relationships between gene expression images. We tested this method using mouse brain section images from the Allen Mouse Brain Atlas public database. This methodology provided measurements able to characterize the similarity of the density distribution between gene expressions and allowed the visualization of the results through networks and Principal Component Analysis (PCA). These visualizations are useful to analyze the similarity level between gene expression patterns, as well as to compare connection patterns between region networks. Some genes were found to have the same type of function and to be near each other in the PCA visualizations. These results suggest cerebral density correlations between gene expressions that could be further explored. (C) 2011 Elsevier B.V. All rights reserved.

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.

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.

Solução rasterizada para o problema de empacotamento de fita irregular utilizando a Montanha Voronoi.

O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta.