Skip to main content
Mathematica

Return to Question

Tweeted twitter.com/StackMma/status/1581661255596580869
added 6 characters in body
Source Link
kirma
kirma
  • 19.1k
  • 1
  • 55
  • 95

I have positions and radii of $n$ $n$-dimensional hyperspheres and want to find their intersection points efficiently. A very-straight-forward solution seems quite reliable:

Timing@With[{d = 50},
  With[{
    p = RandomReal[{-1, 1}, d],
    s = RandomReal[{-1, 1}, {d, d}]},
   Sort[EuclideanDistance[p, #] & /@
     (Array[x, d] /.
       Quiet@Solve[
         Element[Array[x, d], Sphere[#, EuclideanDistance[p, #]]] & /@ s,
         Array[x, d]])]]]

{69.002, {4.84698*10^-14, 0.858948}}

The problem here is that 50-dimensional solution already takes about 70 seconds on my system, and I'd want to find solutions when $n \gg 100$. FindMinimum or NMinimize of sums of squares of sphere surface distances might work to an extent, but these find only one of the solutions. Are there good alternatives to the straight-forward Solve?

I have positions and radii of $n$ $n$-dimensional hyperspheres and want to find their intersection points efficiently. A very-straight-forward solution seems quite reliable:

Timing@With[{d = 50},
  With[{
    p = RandomReal[{-1, 1}, d],
    s = RandomReal[{-1, 1}, {d, d}]},
   Sort[EuclideanDistance[p, #] & /@
     (Array[x, d] /.
       Quiet@Solve[
         Element[Array[x, d], Sphere[#, EuclideanDistance[p, #]]] & /@ s,
         Array[x, d]])]]]

{69.002, {4.84698*10^-14, 0.858948}}

The problem here is that 50-dimensional solution already takes 70 seconds on my system, and I'd want to find solutions when $n \gg 100$. FindMinimum or NMinimize of sums of squares of sphere surface distances might work to an extent, but these find only one of the solutions. Are there good alternatives to the straight-forward Solve?

I have positions and radii of $n$ $n$-dimensional hyperspheres and want to find their intersection points efficiently. A very-straight-forward solution seems quite reliable:

Timing@With[{d = 50},
  With[{
    p = RandomReal[{-1, 1}, d],
    s = RandomReal[{-1, 1}, {d, d}]},
   Sort[EuclideanDistance[p, #] & /@
     (Array[x, d] /.
       Quiet@Solve[
         Element[Array[x, d], Sphere[#, EuclideanDistance[p, #]]] & /@ s,
         Array[x, d]])]]]

{69.002, {4.84698*10^-14, 0.858948}}

The problem here is that 50-dimensional solution already takes about 70 seconds on my system, and I'd want to find solutions when $n \gg 100$. FindMinimum or NMinimize of sums of squares of sphere surface distances might work to an extent, but these find only one of the solutions. Are there good alternatives to the straight-forward Solve?

Source Link
kirma
kirma
  • 19.1k
  • 1
  • 55
  • 95

How to find intersection points of $n$ $n$-spheres reliably and efficiently when $n$ is large

I have positions and radii of $n$ $n$-dimensional hyperspheres and want to find their intersection points efficiently. A very-straight-forward solution seems quite reliable:

Timing@With[{d = 50},
  With[{
    p = RandomReal[{-1, 1}, d],
    s = RandomReal[{-1, 1}, {d, d}]},
   Sort[EuclideanDistance[p, #] & /@
     (Array[x, d] /.
       Quiet@Solve[
         Element[Array[x, d], Sphere[#, EuclideanDistance[p, #]]] & /@ s,
         Array[x, d]])]]]

{69.002, {4.84698*10^-14, 0.858948}}

The problem here is that 50-dimensional solution already takes 70 seconds on my system, and I'd want to find solutions when $n \gg 100$. FindMinimum or NMinimize of sums of squares of sphere surface distances might work to an extent, but these find only one of the solutions. Are there good alternatives to the straight-forward Solve?