# prove a space is epsilon-full of points

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.

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