Skip to main content
3 of 7
added 153 characters in body
eagle34
  • 161
  • 3

Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I'm eventually interested in exploring other metrics as well). So this is a discrete optimization problem where we are minimizing the maximum distance of an element in our set from $p$. However, the side constraint is that these hyperspheres cannot overlap with each other.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric graph, where the weights are the distance from $p$, and we have an adjacency matrix where $A_{i,j} = 1$ if $dist(S_i, S_j) < c$ for some constant $c$, but I'm not sure if there is some other formulation I am missing. Is there a name for this problem?

I am also considering this from a probabilistic perspective, in the case where we can assume that the hyperspheres are uniformly distributed.

eagle34
  • 161
  • 3