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).
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.
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:
The following have contributed to this page