4
$\begingroup$

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$ non overlapping 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 am considering approximating the hyperspheres as axis-aligned hypercubes, but am not sure if this actually simplifies the problem.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric intersection graph (more specifically a disk intersection 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$. 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.

Improve this question
$\endgroup$
6
  • $\begingroup$ I must miss something here: 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. If $p$ is given and the hyperspheres are given you have all distances you want… $\endgroup$
    – Dirk
    Commented Oct 14, 2015 at 11:09
  • $\begingroup$ Yes, the question is one of efficiency - I'd rather not enumerate all possible combinations of K non overlapping hyperspheres. I'd appreciate any commentary on the approximation factor of the greedy approach / other efficient approaches here, or equivalence to known problems. $\endgroup$
    – eagle34
    Commented Oct 14, 2015 at 17:18
  • $\begingroup$ You might try a greedy algorithm. E.g., Sakai, S., Togasaki, M., & Yamazaki, K. (2003). "A note on greedy algorithms for the maximum weighted independent set problem." Discrete Applied Mathematics, 126(2), 313-322. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 14, 2015 at 17:41
  • $\begingroup$ Hi Joseph - Yes, thank you, I have done some reading on greedy approaches for maximum weight independent set in a geometric graph, and it seems that particularly for sparse graphs a greedy approach might be reasonable. However, there is another aspect of this problem - the fact that the weights are geometric as well (the weight of each hypersphere is the distance of its center from $p$) - which existing algorithms for MWIS in a geometric graph doesn't exploit. I would like to compute as few of these distances as possible, so I'm thinking about some kind of pruning strategy. $\endgroup$
    – eagle34
    Commented Oct 14, 2015 at 17:57
  • $\begingroup$ If $N$ is very large, you can imagine arranging your $N$ spheres so that their centers are "nearly dense" in a large neighborhood of $p$ (for some very small $\varepsilon$, there is no $\varepsilon$-ball anywhere close to $p$ not containing the center of one of your spheres). Then your problem looks very much like the Tammes problem (see www-lp.fmf.uni-lj.si/plestenjak/talks/preddvor.pdf). This problem is really hard, so I don't imagine you'll find an efficient way of getting to an exact solution. $\endgroup$
    – Will Brian
    Commented Oct 14, 2015 at 18:05

0

Reset to default

You must log in to answer this question.