What is it about?
We explore spaces by taking one step at a time. This is easy to do in a low dimensional space such as in 2D and 3D which we are familiar with. However, high dimensional spaces are much harder to explore due to the "curse of dimensionality". This paper proposes methods to explore high dimensional spaces. Our key idea is to gradually and locally advance the front of existing samples, by shooting a random ray from an existing sample and then randomly pick the next sample from this ray, until the space is sufficiently saturated. The generated samples, or footsteps, are uniform and yet irregular to well cover the spaces without structured artifacts (alias or bias).
Featured Image
Photo by Rob King on Unsplash
Why is it important?
Sampling is a core component for many scientific and engineering disciplines. Sampling high dimensional spaces has many applications such as approximate Delaunay graph construction, global optimization, and robotic motion planning, and yet remains challenging due to the curse of dimensionality. We propose computationally simple and mathematically proven methods that can sample high dimensional spaces with good coverage and distribution properties.
Perspectives
Computer graphics primarily concerns with 2D and 3D spaces, and thus existing research in sampling focuses mostly on such low dimensional spaces. Higher dimensional spaces remains relatively under-explored, despite practical applications (e.g., geometry, optimization, robotics) and mathematical properties (e.g., curse of dimensionality). Our work provides a simple and effective method, and could be a starting point for further research.
Li-Yi Wei
Adobe Research
Read the Original
This page is a summary of: Spoke-Darts for High-Dimensional Blue-Noise Sampling, ACM Transactions on Graphics, April 2018, ACM (Association for Computing Machinery),
DOI: 10.1145/3194657.
You can read the full text:
Resources
Contributors
The following have contributed to this page
