Scott Mitchell, Data Analysis & Informatics Department, SNL ABQ
Separated-Yet-Dense Random Point Clouds for Meshing and More
Computational geometry is interesting to me because it combines both discrete and continuous objects, and both math and algorithms. I also like it because I can draw pictures to understand what I'm doing. Specifically I'll talk about the work we've done over the past couple of years on point clouds with random positions. We made up the term separated-yet-dense to describe sets of sample points such that no two points of the set are too close to one another, but any other point of the domain is close to some sample point. Computer Graphics has been obsessed with a particular way of generating these kind of point clouds, by selecting points sequentially and spatially uniformly at random. This way is important because it avoids visual artifacts in texture synthesis. Computational Geometry has been obsessed with a different way of generating these kinds of point clouds, by selecting them sequentially and deterministically, by selecting the domain point that is furthest away from the point cloud so far. Nearby points are attached together to generate a finite element mesh. The advantage of this approach is it is faster, and is easier to analyse. We've been coming up with algorithms that combine features of both approaches. Some have theory guarantees, and some are simpler and work better in practice. We have both computer graphics and mesh generation applications, and we've even started using random lines to efficiently solve some uncertainty quantification problems.