Past Event: Oden Institute Seminar

Exploring high-dimensional spaces using Well-spaced Random Points and Hyperplane Sampling with application to Graphics, Meshes, Global Optimization, Uncertainty and Robotics

Mohamed Ebeida, Sandia National Laboratories

Abstract

Well-spaced random points are useful for a host of applications, including sampling for texture synthesis in computer graphics; finite element simplicial and Voronoi meshes for fracture mechanics; sample points for exploring abstract spaces in optimization and uncertainty quantification over scientific simulations; and collision free path planning for robots. These disciplines differ in terms of the dimensions of the space and how the boundaries are handled, but a unifying theme is that since the problems are too large and complex to solve analytically, we must explore the space at specific points, and make informed guesses as to what happens between. Designing point sets with the right properties is essential to get good quality solutions, in a reasonable amount of time. Two recurring and valued properties are "well-spaced," no two sample points are too close together, yet no domain point is too far from a sample; and "random," so that no deterministic patterns spoil the prediction or integration. Computer Graphics has been obsessed with a particular way of generating these kind of point sets, by selecting points sequentially and spatially uniformly at random. Computational Geometry has been obsessed with a different way of generating these kinds of point sets, by selecting them sequentially and deterministically. We've been coming up with algorithms that combine features of both disciplines, and include GPU parallelism. Some algorithms have theory guarantees, and some are simpler and work better in practice. To deal with larger dimensions, we are generalizing point sampling to hyperplane sampling, including sampling recursively by dimension. We have graphics, meshing, uncertainty and optimization, and robotic motion planning applications. DAKOTA is Sandia's open-source software for parallel optimization and uncertainty quantification over large-scale and (mostly) black-box simulations, and is our method for driving many of these applications and giving our work to the community.