We consider a quantity that measures the roundness of a bounded, convex @math -polytope in @math . We majorise this quantity in terms of the smallest singular value of the matrix of outer unit normals to the facets of the polytope.
Similar quantities appear also in the literature on finite volume methods. For example, in @cite_3 , a finite volume method based on Voronoi tessellations of the sphere is constructed, and a regularity norm' is defined for the Voronoi tessellation by minimising the ratio @math over all neighbours of each Voronoi cell @math generated by a point @math on the sphere, and over all Voronoi cells @math in the tessellation. Note that in both @math and @math above are computed with respect to the geodesic metric on the sphere. For any given Voronoi cell @math with generator @math , the smallest value of @math over all generators @math of adjacent Voronoi cells @math resembles the degeneracy ratio of @math defined in . This is because if @math is a Voronoi cell with generator @math , and if @math is small, then @math will be small, and vice versa.
@cite_3
2949722426 2161434505 2114288655 2623449798
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 @math expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the @math 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 @math 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, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest. We first develop and analyze a finite volume scheme for the discretization of partial differential equations (PDEs) on the sphere; the scheme uses Voronoi tessellations of the sphere. For a model convection–diffusion problem, the finite volume scheme is shown to produce first-order accurate approximations with respect to a mesh-dependent discrete firstderivative norm. Then, we introduce the notion of constrained centroidal Voronoi tessellations (CCVTs) of the sphere; these are special Voronoi tessellation of the sphere for which the generators of the Voronoi cells are also the constrained centers of mass, with respect to a prescribed density function, of the cells. After discussing an algorithm for determining CCVT meshes on the sphere, we discuss and illustrate several desirable properties possessed by these meshes. In particular, it is shown that CCVT meshes define very high-quality uniform and non-uniform meshes on the sphere. Finally, we discuss, through some computational experiments, the performance of the CCVT meshes used in conjunction with the finite volume scheme for the solution of simple model PDEs on the sphere. The experiments show, for example, that the CCVT based finite volume approximations are second-order accurate if errors are measured in We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT). Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD), defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd-tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O(mlogn), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches. An algorithm for the generation of non-uniform, locally orthogonal staggered unstructured spheroidal grids is described. This technique is designed to generate very high-quality staggered Voronoi–Delaunay meshes appropriate for general circulation modelling on the sphere, including applications to atmospheric simulation, ocean-modelling and numerical weather prediction. Using a recently developed Frontal-Delaunay refinement technique, a method for the construction of high-quality unstructured spheroidal Delaunay triangulations is introduced. A locally orthogonal polygonal grid, derived from the associated Voronoi diagram, is computed as the staggered dual. It is shown that use of the Frontal-Delaunay refinement technique allows for the generation of very high-quality unstructured triangulations, satisfying a priori bounds on element size and shape. Grid quality is further improved through the application of hill-climbing-type optimisation techniques. Overall, the algorithm is shown to produce grids with very high element quality and smooth grading characteristics, while imposing relatively low computational expense. A selection of uniform and non-uniform spheroidal grids appropriate for high-resolution, multi-scale general circulation modelling are presented. These grids are shown to satisfy the geometric constraints associated with contemporary unstructured C-grid-type finite-volume models, including the Model for Prediction Across Scales (MPAS-O). The use of user-defined mesh-spacing functions to generate smoothly graded, non-uniform grids for multi-resolution-type studies is discussed in detail.