3
$\begingroup$

lets say I have a 5 dimensional grid where each dimension has 10 points. There are 100000 combinations. Let's say I want a subset of 10000, is there a deterministic algorithm that will choose a set of points that "covers" the region the best and converges to the limiting case of choosing every point?

If I had a weighting function for each point, would there be a deterministic algorithm that would tend to choose points that are equidistant in a weighting sense as well?

I can think of some possible ways in lower dimension, just wondering if there is a well defined solution (area of math) for these types of problems that extends to higher dimensions

I've tried searching sampling methods, multi-dimensional sampling and the like, but no luck

$\endgroup$
2
$\begingroup$

Let's talk about the uniform sampling case. Suppose you define some spatially regular ordering for the points on the grid. For the 5 dimensional points, say the first coordinate increases the slowest, then the second increases the next slowest, and so on, and the last coordinate increases the fastest. Denote the ordered set $p_i$ for $i=0,\ldots,N-1$ where $N=100000$ is the total number of points. Let $n$ be the number of points we want to sample. If you take the set of points $$ { p_j: j = (a+iM) \mod N } $$ for arbitrary $a$ and $i=0,\ldots,n$ where $M$ and $N$ are coprime, then the $p_j$ should not repeat until $n = N$. If you choose $a$ and $M$ reasonably ($M$ being quite a bit larger than $N$), then these points will also be relatively uniformly distributed, but perhaps with too much structure and no guarantee that they have the blue noise property.

For the weighted case, you are essentially asking for a combinatorial optimization, so I doubt there would be efficient ways of solving it. On the other hand, your problem size of $10^5$ is not that big.

$\endgroup$
  • $\begingroup$ Combinatorial optimization. I didn't think of it in that regard. I can see how this could be posed similarly to a traveling salesman problem. Basically I want to "fill the space as much as possible" while minimizing the total weight of the space I've visited. Of the combinatorial optimization problems out there, do you know of any that focus on this issue? It seems related to en.wikipedia.org/wiki/K-minimum_spanning_tree (but instead of edge costs I have point costs). $\endgroup$ – phubaba Oct 27 '13 at 18:13
  • $\begingroup$ I've actually found some references to en.wikipedia.org/wiki/Rapidly_exploring_random_tree that may be what I want $\endgroup$ – phubaba Oct 27 '13 at 18:15
2
$\begingroup$

You enumerate your grid points along a space-filling curve. If you then want $M$ out of $N$ points, choose the points with indices $k\frac{N}{M}$, where $k=1\dots M$.

Depending on the curve you use there may be some pathological cases, but in general this should give you a good sampling of your space, assuming the grid point density is more or less homogeneous to begin with.

$\endgroup$
  • $\begingroup$ based on your "space-filling curve" term, a google search with space-filling curve with weights gave this article: sciencedirect.com/science/article/pii/0020019083900364 A fast heuristic based on spacefilling curves for minimum-weight matching in the plane. Unfortunately I can't get access to this paper through my school :( $\endgroup$ – phubaba Oct 27 '13 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.