I am using a radial neighbors algorithm to make predictions but am running in to trouble because my dataset does not populate the whole input/query space, in this case a hypercube from [-1,1] along every dimension in $\mathbb{R}^6$.

Essentially I have a bounded space $U$ and a set of points, $X$, and I need to ensure

$$\exists \ x \in X \ s.t. |u-x| \le \epsilon \ \forall \ u \in U$$

In words: I need the space to be fully populated by points, where "full" means that there is no other point in the space more than $\epsilon$ Minkowski distance away from some point in the set.

I am prepared to judiciously add points to $X$ to meet this condition, preferably by creating new points at the centroids of the "holes", the regions where points from $X$ are all greater than $\epsilon$ distance away. But first I need to detect where these holes are. And then at the end I need to verify my additions have filled the space, iterate the process again if they have not.

What I can think to try

A hypersphere of radius $\epsilon$ in $\mathbb{R}^6$ will of course just have a diameter $2\epsilon$. A hypercube of unit side length in $\mathbb{R}^6$ has a longest length from corner to corner of $\sqrt[p]{6}$, where $p$ is the Minkowski distance parameter. So I can iterate through the space along a grid with points spaced at distance $\frac{2\epsilon}{\sqrt[p]{6}}$ and just fill in holes as I encounter them. But in this scheme I might not be placing new points most effectively, and it might get expensive to do this search, especially if I later end up needing to do it in higher dimension.

I've looked in to space-filling curves, but I am not sure how they can help me aside from maybe providing a different order to search my grid.

This question is almost too mathematical for stackoverflow or cross-validated yet too algorithmic for you all.

  • $\begingroup$ Hello and welcome on Math.SE. Please make sure to include your approaches to the problems as it is indicated here. $\endgroup$
    – SK19
    Commented May 9, 2018 at 15:37
  • 1
    $\begingroup$ Here is an article where they address this problem with rectangles rather than balls arxiv.org/pdf/1704.00683.pdf $\endgroup$ Commented May 9, 2018 at 19:00


You must log in to answer this question.

Browse other questions tagged .