Página 1 dos resultados de 162 itens digitais encontrados em 0.017 segundos

Applications of Voronoi and Delaunay Diagrams in the solution of the geodetic boundary value problem

Quintero,C. A. B.; Escobar,I. P.; Ponte-Neto,C. F.
Fonte: Universidade Federal do Paraná Publicador: Universidade Federal do Paraná
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/09/2012 EN
Relevância na Pesquisa
46.39%
Voronoi and Delaunay structures are presented as discretization tools to be used in numerical surface integration aiming the computation of geodetic problems solutions, when under the integral there is a non-analytical function (e. g., gravity anomaly and height). In the Voronoi approach, the target area is partitioned into polygons which contain the observed point and no interpolation is necessary, only the original data is used. In the Delaunay approach, the observed points are vertices of triangular cells and the value for a cell is interpolated for its barycenter. If the amount and distribution of the observed points are adequate, gridding operation is not required and the numerical surface integration is carried out by point-wise. Even when the amount and distribution of the observed points are not enough, the structures of Voronoi and Delaunay can combine grid with observed points in order to preserve the integrity of the original information. Both schemes are applied to the computation of the Stokes' integral, the terrain correction, the indirect effect and the gradient of the gravity anomaly, in the State of Rio de Janeiro, Brazil area.

The geometric stability of Voronoi diagrams in normed spaces which are not uniformly convex

Reem, Daniel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.47%
The Voronoi diagram is a geometric object which is widely used in many areas. Recently it has been shown that under mild conditions Voronoi diagrams have a certain continuity property: small perturbations of the sites yield small perturbations in the shapes of the corresponding Voronoi cells. However, this result is based on the assumption that the ambient normed space is uniformly convex. Unfortunately, simple counterexamples show that if uniform convexity is removed, then instability can occur. Since Voronoi diagrams in normed spaces which are not uniformly convex do appear in theory and practice, e.g., in the plane with the Manhattan (ell_1) distance, it is natural to ask whether the stability property can be generalized to them, perhaps under additional assumptions. This paper shows that this is indeed the case assuming the unit sphere of the space has a certain (non-exotic) structure and the sites satisfy a certain "general position" condition related to it. The condition on the unit sphere is that it can be decomposed into at most one "rotund part" and at most finitely many non-degenerate convex parts. Along the way certain topological properties of Votonoi cells (e.g., that the induced bisectors are not "fat") are proved.; Comment: 29 pages; 10 figures; Sections 1...

Voronoi cells of discrete point sets

Voigt, Ina
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/11/2008
Relevância na Pesquisa
46.48%
It is well known that all cells of the Voronoi diagram of a Delaunay set are polytopes. For a finite point set, all these cells are still polyhedra. So the question arises, if this observation holds for all discrete point sets: Are always all Voronoi cells of an arbitrary, infinite discrete point set polyhedral? In this paper, an answer to this question will be given. It will be shown that all Voronoi cells of a discrete point set are polytopes if and only if every point of the point set is an inner point. Furthermore, the term of a locally finitely generated discrete point set will be introduced and it will be shown that exactly these sets have the property of possessing only polyhedral Voronoi cells.

New Monte Carlo method for planar Poisson-Voronoi cells

Hilhorst, H. J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/12/2006
Relevância na Pesquisa
36.3%
By a new Monte Carlo algorithm we evaluate the sidedness probability p_n of a planar Poisson-Voronoi cell in the range 3 \leq n \leq 1600. The algorithm is developed on the basis of earlier theoretical work; it exploits, in particular, the known asymptotic behavior of p_n as n\to\infty. Our p_n values all have between four and six significant digits. Accurate n dependent averages, second moments, and variances are obtained for the cell area and the cell perimeter. The numerical large n behavior of these quantities is analyzed in terms of asymptotic power series in 1/n. Snapshots are shown of typical occurrences of extremely rare events implicating cells of up to n=1600 sides embedded in an ordinary Poisson-Voronoi diagram. We reveal and discuss the characteristic features of such many-sided cells and their immediate environment. Their relevance for observable properties is stressed.; Comment: 35 pages including 10 figures and 4 tables

Statistical Topology of Three-Dimensional Poisson-Voronoi Cells and Cell Boundary Networks

Lazar, Emanuel A.; Mason, Jeremy K.; MacPherson, Robert D.; Srolovitz, David J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 08/01/2014
Relevância na Pesquisa
36.34%
Voronoi tessellations of Poisson point processes are widely used for modeling many types of physical and biological systems. In this paper, we analyze simulated Poisson-Voronoi structures containing a total of 250,000,000 cells to provide topological and geometrical statistics of this important class of networks. We also report correlations between some of these topological and geometrical measures. Using these results, we are able to corroborate several conjectures regarding the properties of three-dimensional Poisson-Voronoi networks and refute others. In many cases, we provide accurate fits to these data to aid further analysis. We also demonstrate that topological measures represent powerful tools for describing cellular networks and for distinguishing among different types of networks.; Comment: 15 pages, 19 figures, Supplemental Material included

On the size-distribution of Poisson Voronoi cells

Jarai-Szabo, F.; Neda, Z.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.34%
Poisson Voronoi diagrams are useful for modeling and describing various natural patterns and for generating random lattices. Although this particular space tessellation is intensively studied by mathematicians, in two- and three dimensional spaces there is no exact result known for the size-distribution of Voronoi cells. Motivated by the simple form of the distribution function in the one-dimensional case, a simple and compact analytical formula is proposed for approximating the Voronoi cell's size distribution function in the practically important two- and three dimensional cases as well. Denoting the dimensionality of the space by d (d=1,2,3) the $f(y)=Const*y^{(3d-1)/2}exp(-(3d+1)y/2)$ compact form is suggested for the normalized cell-size distribution function. By using large-scale computer simulations the validity of the proposed distribution function is studied and critically discussed.; Comment: 12 pages, 6 figures

Improving Rogers' upper bound for the density of unit ball packings via estimating the surface area of Voronoi cells from below in Euclidean d-space for all d>7

Bezdek, Karoly
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/10/2001
Relevância na Pesquisa
46.14%
The sphere packing problem asks for the densest packing of unit balls in d-dimensional Euclidean space. This problem has its roots in geometry, number theory and it is part of Hilbert's 18th problem. In 1958 C. A. Rogers proved a non-trivial upper bound for the density of unit ball packings in d-dimensional Euclidean space for all d>0. In 1978 Kabatjanskii and Levenstein improved this bound for large d. In fact, Rogers' bound is the presently known best bound for 43>d>3, and above that the Kabatjanskii-Levenstein bound takes over. In this paper we improve Rogers' upper bound for the density of unit ball packings in Euclidean d-space for all d>7. We do this by estimating from below the surface area of Voronoi cells in any packing of unit balls in Euclidean d-space for all d>7.; Comment: to be published in Discrete and Comput. Geom

Edge Detecting New Physics the Voronoi Way

Debnath, Dipsikha; Gainer, James S.; Kim, Doojin; Matchev, Konstantin T.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/06/2015
Relevância na Pesquisa
36.36%
We point out that interesting features in high energy physics data can be determined from properties of Voronoi tessellations of the relevant phase space. For illustration, we focus on the detection of kinematic "edges" in two dimensions, which may signal physics beyond the standard model. After deriving some useful geometric results for Voronoi tessellations on perfect grids, we propose several algorithms for tagging the Voronoi cells in the vicinity of kinematic edges in real data. We show that the efficiency is improved by the addition of a few Voronoi relaxation steps via Lloyd's method. By preserving the maximum spatial resolution of the data, Voronoi methods can be a valuable addition to the data analysis toolkit at the LHC.; Comment: 6 pages, 7 figures

Set Reconstruction by Voronoi cells

Reitzner, Matthias; Spodarev, Evgeny; Zaporozhets, Dmitry
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.26%
For a Borel set $A$ and a homogeneous Poisson point process $\eta$ in $\R^d$ of intensity $\lambda >0$, define the Poisson--Voronoi approximation $ A_\eta$ of $A$ as a union of all Voronoi cells with nuclei from $\eta$ lying in $A$. If $A$ has a finite volume and perimeter we find an exact asymptotic of $\E\Vol(A\Delta A_\eta)$ as $\lambda\to\infty$ where $\Vol$ is the Lebesgue measure. Estimates for all moments of $\Vol(A_\eta)$ and $\Vol(A\Delta A_\eta)$ together with their asymptotics for large $\lambda$ are obtained as well.; Comment: 19 pages, minor revisions

Characterization of maximally random jammed sphere packings: Voronoi correlation functions

Klatt, Michael Andreas; Torquato, Salvatore
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/01/2015
Relevância na Pesquisa
36.59%
We characterize the structure of maximally random jammed (MRJ) sphere packings by computing the Minkowski functionals (volume, surface area, and integrated mean curvature) of their associated Voronoi cells. The probability distribution functions of these functionals of Voronoi cells in MRJ sphere packings are qualitatively similar to those of an equilibrium hard-sphere liquid and partly even to the uncorrelated Poisson point process, implying that such local statistics are relatively structurally insensitive. This is not surprising because the Minkowski functionals of a single Voronoi cell incorporate only local information and are insensitive to global structural information. To improve upon this, we introduce descriptors that incorporate nonlocal information via the correlation functions of the Minkowski functionals of two cells at a given distance as well as certain cell-cell probability density functions. We evaluate these higher-order functions for our MRJ packings as well as equilibrium hard spheres and the Poisson point process. We find strong anticorrelations in the Voronoi volumes for the hyperuniform MRJ packings, consistent with previous findings for other pair correlations [A. Donev et al., Phys. Rev. Lett. 95, 090604 (2005)]...

Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing

Bonifas, Nicolas; Dadush, Daniel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/12/2014
Relevância na Pesquisa
36.42%
Improving on the Voronoi cell based techniques of Micciancio and Voulgaris (SIAM J. Comp. 13), and Sommer, Feder and Shalvi (SIAM J. Disc. Math. 09), we give a Las Vegas $\tilde{O}(2^n)$ expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the $\tilde{O}(4^n)$ deterministic runtime of the Micciancio Voulgaris algorithm, henceforth MV, for CVPP (which also solves CVP) at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the $\tilde{O}(4^n)$ path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work...

The geometric stability of Voronoi diagrams with respect to small changes of the sites

Reem, Daniel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.45%
Voronoi diagrams appear in many areas in science and technology and have numerous applications. They have been the subject of extensive investigation during the last decades. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Consider the following question: does a small change of the sites, e.g., of their position or shape, yield a small change in the corresponding Voronoi cells? This question is by all means natural and fundamental, since in practice one approximates the sites either because of inexact information about them, because of inevitable numerical errors in their representation, for simplification purposes and so on, and it is important to know whether the resulting Voronoi cells approximate the real ones well. The traditional approach to Voronoi diagrams, and, in particular, to (variants of) this question, is combinatorial. However, it seems that there has been a very limited discussion in the geometric sense (the shape of the cells), mainly an intuitive one, without proofs, in Euclidean spaces. We formalize this question precisely, and then show that the answer is positive in the case of R^d, or, more generally...

From symmetry break to Poisson point process in 2D Voronoi tessellations: the generic nature of hexagons

Lucarini, Valerio
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/08/2007
Relevância na Pesquisa
36.57%
We bridge the properties of the regular square and honeycomb Voronoi tessellations of the plane to those of the Poisson-Voronoi case, thus analyzing in a common framework symmetry-break processes and the approach to uniformly random distributions of tessellation-generating points. We consider ensemble simulations of tessellations generated by points whose regular positions are perturbed through a Gaussian noise controlled by the parameter alpha. We study the number of sides, the area, and the perimeter of the Voronoi cells. For alpha>0, hexagons are the most common class of cells, and 2-parameter gamma distributions describe well the statistics of the geometrical characteristics. The symmetry break due to noise destroys the square tessellation, whereas the honeycomb hexagonal tessellation is very stable and all Voronoi cells are hexagon for small but finite noise with alpha<0.1. For a moderate amount of Gaussian noise, memory of the specific unperturbed tessellation is lost, because the statistics of the two perturbed tessellations is indistinguishable. When alpha>2, results converge to those of Poisson-Voronoi tessellations. The properties of n-sided cells change with alpha until the Poisson-Voronoi limit is reached for alpha>2. The Desch law for perimeters is confirmed to be not valid and a square root dependence on n is established. The ensemble mean of the cells area and perimeter restricted to the hexagonal cells coincides with the full ensemble mean; this might imply that the number of sides acts as a thermodynamic state variable fluctuating about n=6; this reinforces the idea that hexagons...

Voronoi Cells of Lattices with Respect to Arbitrary Norms

Blömer, Johannes; Kohn, Kathlén
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.58%
Motivated by the deterministic single exponential time algorithm of Micciancio and Voulgaris for solving the shortest and closest vector problem for the Euclidean norm, we study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms. On the positive side, we show that for strictly convex and smooth norms the geometry of Voronoi cells of lattices in any dimension is similar to the Euclidean case, i.e., the Voronoi cells are defined by the so-called Voronoi-relevant vectors and the facets of a Voronoi cell are in one-to-one correspondence with these vectors. On the negative side, we show that combinatorially Voronoi cells for arbitrary strictly convex and smooth norms are much more complicated than in the Euclidean case. In particular, we construct a family of three-dimensional lattices whose number of Voronoi-relevant vectors with respect to the $\ell_3$-norm is unbounded. Since the algorithm of Micciancio and Voulgaris and its run time analysis crucially depend on the fact that for the Euclidean norm the number of Voronoi-relevant vectors is single exponential in the lattice dimension, this indicates that the techniques of Micciancio and Voulgaris cannot be extended to achieve deterministic single exponential time algorithms for lattice problems with respect to arbitrary $\ell_p$-norms.

Complexity and algorithms for computing Voronoi cells of lattices

Sikiric, Mathieu Dutour; Schuermann, Achill; Vallentin, Frank
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.26%
In this paper we are concerned with finding the vertices of the Voronoi cell of a Euclidean lattice. Given a basis of a lattice, we prove that computing the number of vertices is a #P-hard problem. On the other hand we describe an algorithm for this problem which is especially suited for low dimensional (say dimensions at most 12) and for highly-symmetric lattices. We use our implementation, which drastically outperforms those of current computer algebra systems, to find the vertices of Voronoi cells and quantizer constants of some prominent lattices.; Comment: 20 pages, 2 figures, 5 tables

Many-faced cells and many-edged faces in 3D Poisson-Voronoi tessellations

Hilhorst, H. J.; Lazar, E. A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.32%
Motivated by recent new Monte Carlo data we investigate a heuristic asymptotic theory that applies to n-faced 3D Poisson-Voronoi cells in the limit of large n. We show how this theory may be extended to n-edged cell faces. It predicts the leading order large-n behavior of the average volume and surface area of the n-faced cell, and of the average area and perimeter of the n-edged face. Such a face is shown to be surrounded by a toroidal region of volume n/lambda (with lambda the seed density) that is void of seeds. Two neighboring cells sharing an n-edged face are found to have their seeds at a typical distance that scales as n^{-1/6} and whose probability law we determine. We present a new data set of 4*10^9 Monte Carlo generated 3D Poisson-Voronoi cells, larger than any before. Full compatibility is found between the Monte Carlo data and the theory. Deviations from the asymptotic predictions are explained in terms of subleading corrections whose powers in n we estimate from the data.; Comment: 25 pages, 14 figures, slightly expanded version

Polyhedral Voronoi Cells

Voigt, Ina; Weis, Stephan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/03/2010
Relevância na Pesquisa
46.2%
Voronoi cells of a discrete set in Euclidean space are known as generalized polyhedra. We identify polyhedral cells of a discrete set through a direction cone. For an arbitrary set we distinguish polyhedral from non-polyhedral cells using inversion at a sphere and a theorem of semi-infinite linear programming.; Comment: 12 pages, 6 figures

Voronoi and Voids Statistics for Super-homogeneous Point Processes

Gabrielli, Andrea; Torquato, Salvatore
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 06/05/2004
Relevância na Pesquisa
36.49%
We study the Voronoi and void statistics of super-homogeneous (or hyperuniform) point patterns in which the infinite-wavelength density fluctuations vanish. Super-homogeneous or hyperuniform point patterns arise in one-component plasmas, primordial density fluctuations in the Universe, and in jammed hard-particle packings. We specifically analyze a certain one-dimensional model by studying size fluctuations and correlations of the associated Voronoi cells. We derive exact results for the complete joint statistics of the size of two Voronoi cells. We also provide a sum rule that the correlation matrix for the Voronoi cells must obey in any space dimension. In contrast to the conventional picture of super-homogeneous systems, we show that infinitely large Voronoi cells or voids can exist in super-homogeneous point processes in any dimension. We also present two heuristic conditions to identify and classify any super-homogeneous point process in terms of the asymptotic behavior of the void size distribution.; Comment: 27 pages, and 4 figures

On spatial thinning-replacement processes based on Voronoi cells

Borovkov, Konstantin; Odell, David
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 19/10/2006
Relevância na Pesquisa
46.26%
We introduce a new class of spatial-temporal point processes based on Voronoi tessellations. At each step of such a process, a point is chosen at random according to a distribution determined by the associated Voronoi cells. The point is then removed, and a new random point is added to the configuration. The dynamics are simple and intuitive and could be applied to modeling natural phenomena. We prove ergodicity of these processes under wide conditions.; Comment: 17 pages, 4 figures

APPLICATIONS OF VORONOI AND DELAUNAY DIAGRAMS IN THE SOLUTION OF THE GEODETIC BOUNDARY VALUE PROBLEM

QUINTERO, C. A. B.; Observatório Nacional, Ministério da Ciência e Tecnologia; ESCOBAR, I. P.; Departamento de Engenharia Cartográfica, Universidade do Estado do Rio de Janeiro; Ponte-NETO, C. F.; Observatório Nacional, Ministério da Ciência e Tecn
Fonte: Universidade Federal do Paraná-UFPR Publicador: Universidade Federal do Paraná-UFPR
Tipo: info:eu-repo/semantics/article; info:eu-repo/semantics/publishedVersion; Artigo Avaliado pelos Pares Formato: application/pdf
Publicado em 26/09/2012 POR
Relevância na Pesquisa
46.39%
Voronoi and Delaunay structures are presented as discretization tools to be used innumerical surface integration aiming the computation of geodetic problemssolutions, when under the integral there is a non-analytical function (e. g., gravityanomaly and height). In the Voronoi approach, the target area is partitioned intopolygons which contain the observed point and no interpolation is necessary, onlythe original data is used. In the Delaunay approach, the observed points are verticesof triangular cells and the value for a cell is interpolated for its barycenter. If theamount and distribution of the observed points are adequate, gridding operation isnot required and the numerical surface integration is carried out by point-wise. Evenwhen the amount and distribution of the observed points are not enough, thestructures of Voronoi and Delaunay can combine grid with observed points in orderto preserve the integrity of the original information. Both schemes are applied to thecomputation of the Stokes’ integral, the terrain correction, the indirect effect and thegradient of the gravity anomaly, in the State of Rio de Janeiro, Brazil area.