Search NASA⌕ Search

SEARCH · Search NASA

Results for “Voronoi”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS2017

JIGSAW-GEO (1.0): Locally Orthogonal Staggered Unstructured Grid Generation for General Circulation Modelling on the Sphere

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

geophysical fluid dynamics↗
NASA NTRS1985

Three-dimensional algorithms for grid restructuring in Free-Lagrangian calculations

Grid restructuring algorithms which lower the price of three-dimensional Free-Lagrange calculations are presented. The algorithms are first given for the case of planar triangulated surfaces embedded in and spanning a three-dimensional region. The tetrahedra generated by this technique form a Delaunay mesh if the interplane spacing is comparable to the resolution within the planes. The algorithm can therefore be used for efficient determinations of Voronoi connections for initial grids. Modifications of the algorithm for the case of closely spaced surfaces are demonstrated in the context of restructuring algorithms which can accommodate colliding surfaces. Then, the restriction to planar surfaces is removed and regular surfaces are examined. The basic algorithm is the same, with an additional operation to project the vertices of one surface onto another. Finally, vertices on the surface are allowed to migrate anywhere in space.

Fritts, M.↗
NASA NTRS1988

Search Problems in Mission Planning and Navigation of Autonomous Aircraft

An architecture for the control of an autonomous aircraft is presented. The architecture is a hierarchical system representing an anthropomorphic breakdown of the control problem into planner, navigator, and pilot systems. The planner system determines high level global plans from overall mission objectives. This abstract mission planning is investigated by focusing on the Traveling Salesman Problem with variations on local and global constraints. Tree search techniques are applied including the breadth first, depth first, and best first algorithms. The minimum-column and row entries for the Traveling Salesman Problem cost matrix provides a powerful heuristic to guide these search techniques. Mission planning subgoals are directed from the planner to the navigator for planning routes in mountainous terrain with threats. Terrain/threat information is abstracted into a graph of possible paths for which graph searches are performed. It is shown that paths can be well represented by a search graph based on the Voronoi diagram of points representing the vertices of mountain boundaries. A comparison of Dijkstra's dynamic programming algorithm and the A* graph search algorithm from artificial intelligence/operations research is performed for several navigation path planning examples. These examples illustrate paths that minimize a combination of distance and exposure to threats. Finally, the pilot system synthesizes the flight trajectory by creating the control commands to fly the aircraft.

Krozel, James A.↗
NASA NTRS1987

Robot path planning with distance-safety criterion

A method for determining an optimal path with a weighted distance-safety criterion is developed. The goal is to strike a compromise between the shortest path and the centerline path, which is safer. The method is composed of three parts: (i) construction of a region map by dividing the workspace, (ii) interregion optimization to determine the entry and departure points of the path in each region, and (iii) intraregion optimization for determining the (optimal) path segment within each region. The region map is generated by using an approximate Voronoi diagram, and region optimization is achieved using variational dynamic programming. Although developed for 2-D problems, the method can be easily extended to a class of 3-D problems. Numerical examples are presented to demonstrate the method.

Suh, Suk-Hwan↗
NASA NTRS1988

Discretization formulas for unstructured grids

The Galerkin weighted residual technique using linear triangular weight functions is employed to develop finite difference formula in cartesian coordinates for the Laplacian operator, first derivative operators and the function for unstructured triangular grids. The weighted residual coefficients associated with the weak formulation of the Laplacian operator are shown to agree with the Taylor series approach on a global average. In addition, a simple algorithm is presented to determine the Voronoi (finite difference) area of an unstructured grid.

Baumeister, Kenneth J.↗
NASA NTRS1989

Learned navigation in unknown terrains: A retraction method

The problem of learned navigation of a circular robot R, of radius delta (is greater than or equal to 0), through a terrain whose model is not a-priori known is considered. Two-dimensional finite-sized terrains populated by an unknown (but, finite) number of simple polygonal obstacles are also considered. The number and locations of the vertices of each obstacle are unknown to R. R is equipped with a sensor system that detects all vertices and edges that are visible from its present location. In this context two problems are covered. In the visit problem, the robot is required to visit a sequence of destination points, and in the terrain model acquisition problem, the robot is required to acquire the complete model of the terrain. An algorithmic framework is presented for solving these two problems using a retraction of the freespace onto the Voronoi diagram of the terrain. Algorithms are then presented to solve the visit problem and the terrain model acquisition problem.

Rao, Nageswara S. V.↗
NASA NTRS1988

Discretization formulas for unstructured grids

The Galerkin weighted residual technique using linear triangular weight functions is employed to develop finite difference formula in cartesian coordinates for the Laplacian operator, first derivative operators and the function for unstructured triangular grids. The weighted residual coefficients associated with the weak formulation of the Laplacian operator are shown to agree with the Taylor series approach on a global average. In addition, a simple algorithm is presented to determine the Voronoi (finite difference) area of an unstructured grid.

Baumeister, Kenneth J.↗
NASA NTRS1991

The evolution of void-filled cosmological structures

1D, 2D, and 3D simulations are used here to investigate the salient features in the evolution of void-filled cosmological structures in universes with arbitrary values of Omega. It is found that the growth of a void as a function of time decreases significantly at the time corresponding to Omega = 0.5. In models constructed in 2D and 3D, suitable initial conditions lead to cellular structure with faceted voids similar to those observed in redshift surveys. Matter compressed to planes flows more rapidly toward condensations at the intersections than would be expected for spherical infall. The peculiar streaming velocities for void diameters of 5000 km/s should be observable. The simulations provide a more physical basis and dynamics for the bubbly and Voronois tesselation models used to derive statistical properties of cellular large-scale structure.

Regos, Eniko↗
NASA NTRS1992

Statistical crystallography of surface micelle spacing

The aggregation of the recently reported surface micelles of block polyelectrolytes is analyzed using techniques of statistical crystallography. A polygonal lattice (Voronoi mosaic) connects center-to-center points, yielding statistical agreement with crystallographic predictions; Aboav-Weaire's law and Lewis's law are verified. This protocol supplements the standard analysis of surface micelles leading to aggregation number determination and, when compared to numerical simulations, allows further insight into the random partitioning of surface films. In particular, agreement with Lewis's law has been linked to the geometric packing requirements of filling two-dimensional space which compete with (or balance) physical forces such as interfacial tension, electrostatic repulsion, and van der Waals attraction.

Noever, David A.↗
NASA NTRS1993

Certification trails and software design for testability

Design techniques which may be applied to make program testing easier were investigated. Methods for modifying a program to generate additional data which we refer to as a certification trail are presented. This additional data is designed to allow the program output to be checked more quickly and effectively. Certification trails were described primarily from a theoretical perspective. A comprehensive attempt to assess experimentally the performance and overall value of the certification trail method is reported. The method was applied to nine fundamental, well-known algorithms for the following problems: convex hull, sorting, huffman tree, shortest path, closest pair, line segment intersection, longest increasing subsequence, skyline, and voronoi diagram. Run-time performance data for each of these problems is given, and selected problems are described in more detail. Our results indicate that there are many cases in which certification trails allow for significantly faster overall program execution time than a 2-version programming approach, and also give further evidence of the breadth of applicability of this method.

Sullivan, Gregory F.↗
NASA NTRS1995

Covolume solutions of three dimensional div-curl equations

Delaunay-Voronoi mesh systems provide a generalization of the classical rectangular staggered meshes to unstructured meshes. It is shown how such 'covolume' discretizations may be applied to div-curl systems in three dimensions. Error estimates are proved and confirmed by a numerical illustration.

Nicolaides, R. A.↗
NASA NTRS1995

Algorithms for high aspect ratio oriented triangulations

Grid generation plays an integral part in the solution of computational fluid dynamics problems for aerodynamics applications. A major difficulty with standard structured grid generation, which produces quadrilateral (or hexahedral) elements with implicit connectivity, has been the requirement for a great deal of human intervention in developing grids around complex configurations. This has led to investigations into unstructured grids with explicit connectivities, which are primarily composed of triangular (or tetrahedral) elements, although other subdivisions of convex cells may be used. The existence of large gradients in the solution of aerodynamic problems may be exploited to reduce the computational effort by using high aspect ratio elements in high gradient regions. However, the heuristic approaches currently in use do not adequately address this need for high aspect ratio unstructured grids. High aspect ratio triangulations very often produce the large angles that are to be avoided. Point generation techniques based on contour or front generation are judged to be the most promising in terms of being able to handle complicated multiple body objects, with this technique lending itself well to adaptivity. The eventual goal encompasses several phases: first, a partitioning phase, in which the Voronoi diagram of a set of points and line segments (the input set) will be generated to partition the input domain; second, a contour generation phase in which body-conforming contours are used to subdivide the partition further as well as introduce the foundation for aspect ratio control, and; third, a Steiner triangulation phase in which points are added to the partition to enable triangulation while controlling angle bounds and aspect ratio. This provides a combination of the advancing front/contour techniques and refinement. By using a front, aspect ratio can be better controlled. By using refinement, bounds on angles can be maintained, while attempting to minimize the number of Steiner points.

Posenau, Mary-Anne K.↗
NASA NTRS1994

Microwave background fluctuations due to the Sunyaev-Zel'dovich effects in pancakes

We calculate distortions in the microwave background radiation from the Sunyaev-Zel'dovich effect, produced by hot gas in large (approximately 100 Mpc) pancakes. The large-scale distribution of the pancakes is taken to be that of a Voronoi foam. Fluctuations for this scenario are estimated to be on the order of delta T/T is approximately 10(exp -5). Using computer simulations, we produce several 32 deg x 32 deg images with 0.25 deg resolution. These images show characteristic linear features produced when a pancake is viewed nearly edge-on. By calculating the two-point and the degenerate three-point correlation functions, we are able to statistically detect such non-Gaussian features even in the presence of a relatively large amount of Gaussian noise. The degenerate three-point correlation function is found to be particularly useful since it is insensitive to correlated Gaussian noise. We also smooth our data over a 7 deg Full Width at Half Maximum (FWHM) Gaussian window to simulate the Cosmic Background Explorer Satellite (COBE) observations. We find that under such low-resolution conditions, the features are highly suppressed.

Subbarao, M. U.↗
NASA NTRS2000

Assessment of Internal Fabric of Particulate Materials

Particle arrangement and distribution within a soil matrix has long been recognized as having significant influence on the mechanical behavior of cohesionless soils. It is well known that two soil specimens having the same grain type (e.g., quartz, feldspar, etc.), same grain size distribution and relative density (or void ratio) can display completely different mechanical behavior. Because of the different fabric configurations in the otherwise similar specimens, they are likely to have different mechanical properties such as stress-strain response, anisotropy, dilatancy, etc. Soil Fabric is defined as the arrangement of particles, particle groups and associated pore space. In the literature, fabric analysis techniques are mainly classified as destructive (e.g., specimen stabilization, thin-sectioning, and microscopy), and nondestructive techniques (e.g., magnetic resonance imaging, ultrasonic testing, x-ray radiography, and computed tomography). Quantifying the void ratio and its distribution is the main parameter used to describe the fabric of particulate materials. This paper presents a comprehensive literature review of fabric analysis techniques applied to particulate materials. In addition, the results of a comprehensive investigation to quantify void ratio of sand specimens will be presented and discussed. The sand used in the experiments in a natural, uniform rounded to sub-rounded silica sand known as F-75 banding sand with mean particle size of 0.22 mm. Uniform specimens and specimens subjected to different axial-strain levels tested under triaxial and biaxial conditions are examined to evaluate void ratio evolution and its distribution using destructive thin-sectioning and nondestructive Computed Tomography (CT) techniques. Details of a new innovative polygon generation technique called Voronoi tessellation used to quantify void ratio of microscopic images of sand grains will be presented and compared to classical Oda's method. Finally, frequency distribution of void ratio calculated using CT analysis will be presented and discussed.

Alshibi, Khalid A.↗
NASA NTRS2000

Interference Lattice-based Loop Nest Tilings for Stencil Computations

A common method for improving performance of stencil operations on structured multi-dimensional discretization grids is loop tiling. Tile shapes and sizes are usually determined heuristically, based on the size of the primary data cache. We provide a lower bound on the numbers of cache misses that must be incurred by any tiling, and a close achievable bound using a particular tiling based on the grid interference lattice. The latter tiling is used to derive highly efficient loop orderings. The total number of cache misses of a code is the sum of (necessary) cold misses and misses caused by elements being dropped from the cache between successive loads (replacement misses). Maximizing temporal locality is equivalent to minimizing replacement misses. Temporal locality of loop nests implementing stencil operations is optimized by tilings that avoid data conflicts. We divide the loop nest iteration space into conflict-free tiles, derived from the cache miss equation. The tiling involves the definition of the grid interference lattice an equivalence class of grid points whose images in main memory map to the same location in the cache-and the construction of a special basis for the lattice. Conflicts only occur on the boundaries of the tiles, unless the tiles are too thin. We show that the surface area of the tiles is bounded for grids of any dimensionality, and for caches of any associativity, provided the eccentricity of the fundamental parallelepiped (the tile spanned by the basis) of the lattice is bounded. Eccentricity is determined by two factors, aspect ratio and skewness. The aspect ratio of the parallelepiped can be bounded by appropriate array padding. The skewness can be bounded by the choice of a proper basis. Combining these two strategies ensures that pathologically thin tiles are avoided. They do not, however, minimize replacement misses per se. The reason is that tile visitation order influences the number of data conflicts on the tile boundaries. If two adjacent tiles are visited successively, there will be no replacement misses on the shared boundary. The iteration space may be covered with pencils larger than the size of the cache while avoiding data conflicts if the pencils are traversed by a scanning-face method. Replacement misses are incurred only on the boundaries of the pencils, and the number of misses is minimized by maximizing the volume of the scanning face, not the volume of the tile. We present an algorithm for constructing the most efficient scanning face for a given grid and stencil operator. In two dimensions it is based on a continued fraction algorithm. In three dimensions it follows Voronoi's successive minima algorithm. We show experimental results of using the scanning face, and compare with canonical loop orderings.

VanderWijngaart, Rob F.↗
NASA NTRS2005

Modeling for Ultrasonic Health Monitoring of Foams with Embedded Sensors

In this report analytical and numerical methods are proposed to estimate the effective elastic properties of regular and random open-cell foams. The methods are based on the principle of minimum energy and on structural beam models. The analytical solutions are obtained using symbolic processing software. The microstructure of the random foam is simulated using Voronoi tessellation together with a rate-dependent random close-packing algorithm. The statistics of the geometrical properties of random foams corresponding to different packing fractions have been studied. The effects of the packing fraction on elastic properties of the foams have been investigated by decomposing the compliance into bending and axial compliance components. It is shown that the bending compliance increases and the axial compliance decreases when the packing fraction increases. Keywords: Foam; Elastic properties; Finite element; Randomness

Wang, L.↗
NASA NTRS2010

Three Dimensional Sector Design with Optimal Number of Sectors

In the national airspace system, sectors get overloaded due to high traffic demand and inefficient airspace designs. Overloads can be eliminated in some cases by redesigning sector boundaries. This paper extends the Voronoi-based sector design method by automatically selecting the number of sectors, allowing three-dimensional partitions, and enforcing traffic pattern conformance. The method was used to design sectors at Fort-Worth and Indianapolis centers for current traffic scenarios. Results show that new designs can eliminate overloaded sectors, although not in all cases, reduce the number of necessary sectors, and conform to major traffic patterns. Overall, the new methodology produces enhanced and efficient sector designs.

Xue, Min↗
NASA NTRS2005

Self-Organizing-Map Program for Analyzing Multivariate Data

SOM_VIS is a computer program for analysis and display of multidimensional sets of Earth-image data typified by the data acquired by the Multi-angle Imaging Spectro-Radiometer [MISR (a spaceborne instrument)]. In SOM_VIS, an enhanced self-organizing-map (SOM) algorithm is first used to project a multidimensional set of data into a nonuniform three-dimensional lattice structure. The lattice structure is mapped to a color space to obtain a color map for an image. The Voronoi cell-refinement algorithm is used to map the SOM lattice structure to various levels of color resolution. The final result is a false-color image in which similar colors represent similar characteristics across all its data dimensions. SOM_VIS provides a control panel for selection of a subset of suitably preprocessed MISR radiance data, and a control panel for choosing parameters to run SOM training. SOM_VIS also includes a component for displaying the false-color SOM image, a color map for the trained SOM lattice, a plot showing an original input vector in 36 dimensions of a selected pixel from the SOM image, the SOM vector that represents the input vector, and the Euclidean distance between the two vectors.

Li, P. Peggy↗