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

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

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.

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

36.47%

#Computer Science - Computational Geometry#Mathematics - Functional Analysis#46N99, 68U05, 46B20, 65D18#F.2.2#G.0#I.3.5

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...

Link permanente para citações:

## Voronoi cells of discrete point sets

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.

Link permanente para citações:

## New Monte Carlo method for planar Poisson-Voronoi cells

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 08/01/2014

Relevância na Pesquisa

36.34%

#Physics - Computational Physics#Condensed Matter - Disordered Systems and Neural Networks#Condensed Matter - Soft Condensed Matter

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

Link permanente para citações:

## On the size-distribution of Poisson Voronoi cells

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

Link permanente para citações:

## 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

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

Link permanente para citações:

## Edge Detecting New Physics the Voronoi Way

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

Link permanente para citações:

## Set Reconstruction by Voronoi cells

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

Link permanente para citações:

## Characterization of maximally random jammed sphere packings: Voronoi correlation functions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 03/01/2015

Relevância na Pesquisa

36.59%

#Condensed Matter - Statistical Mechanics#Condensed Matter - Soft Condensed Matter#82B21, 82B44, 82D30, 82D15, 60G55, 62M30, 62H05, 62H20, 53C65,
05B40, 05B45, 52B05

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)]...

Link permanente para citações:

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

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

36.45%

#Computer Science - Computational Geometry#Mathematics - Functional Analysis#46N99, 68U05, 46B20, 65D18#F.2.2#G.0#I.3.5

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 07/08/2007

Relevância na Pesquisa

36.57%

#Condensed Matter - Statistical Mechanics#Condensed Matter - Disordered Systems and Neural Networks#Computer Science - Computational Geometry#Mathematical Physics#Physics - Data Analysis, Statistics and Probability

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...

Link permanente para citações:

## Voronoi Cells of Lattices with Respect to Arbitrary Norms

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

46.58%

#Mathematics - Metric Geometry#Computer Science - Computational Geometry#Mathematics - Combinatorics

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.

Link permanente para citações:

## Complexity and algorithms for computing Voronoi cells of lattices

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

46.26%

#Mathematics - Metric Geometry#Computer Science - Computational Geometry#Computer Science - Information Theory#Mathematics - Number Theory#11H56, 11H06, 11B1, 03D15, 52B55, 52B12

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

Link permanente para citações:

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

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

Link permanente para citações:

## Polyhedral Voronoi Cells

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

Link permanente para citações:

## Voronoi and Voids Statistics for Super-homogeneous Point Processes

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

Link permanente para citações:

## On spatial thinning-replacement processes based on Voronoi cells

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

Link permanente para citações:

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

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%

#Geociências#Geodésia#2-D tessellation#Delaunay Triangulation#Voronoi Cells#Geodesy#Stokes’ Integral

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.

Link permanente para citações: