Timeline for Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2015 at 18:07 | comment | added | eagle34 | Thank you - I will read through these slides. I'm fairly certain this is an NP hard problem, so I don't hope for an efficient exact solution, but rather some way of preprocessing these spheres so given a point $p$ I can efficiently find an approximate solution. | |
| Oct 14, 2015 at 18:05 | comment | added | Will Brian | 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. | |
| Oct 14, 2015 at 17:57 | comment | added | eagle34 | 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. | |
| Oct 14, 2015 at 17:41 | comment | added | Joseph O'Rourke | 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. | |
| Oct 14, 2015 at 17:18 | comment | added | eagle34 | 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. | |
| Oct 14, 2015 at 17:16 | history | edited | eagle34 | CC BY-SA 3.0 |
added 16 characters in body
|
| Oct 14, 2015 at 11:09 | comment | added | Dirk | 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… | |
| Oct 14, 2015 at 7:59 | history | edited | eagle34 | CC BY-SA 3.0 |
added 137 characters in body
|
| Oct 14, 2015 at 7:54 | history | edited | eagle34 | CC BY-SA 3.0 |
added 137 characters in body
|
| Oct 14, 2015 at 7:33 | history | edited | eagle34 | CC BY-SA 3.0 |
added 13 characters in body
|
| Oct 14, 2015 at 7:09 | history | edited | eagle34 | CC BY-SA 3.0 |
added 153 characters in body
|
| Oct 14, 2015 at 7:01 | history | edited | eagle34 | CC BY-SA 3.0 |
added 4 characters in body
|
| Oct 14, 2015 at 6:57 | review | First posts | |||
| Oct 14, 2015 at 7:06 | |||||
| Oct 14, 2015 at 6:55 | history | asked | eagle34 | CC BY-SA 3.0 |