2

I am a comp.sci. and am not sure if there is a more efficient way to to this: given a discreet uniform grid, compute distance between grid points, right now I do it with the pyth. thm. is there any other way since this is a discrete and uniform grid squares are fixed uniform size. thanks.

mihajlv
  • 121
  • 1
    The pythagorean theorem is probably the best way to go about this. – qaphla Aug 07 '13 at 00:17
  • 1
    Do you perhaps want to calculate the Manhattan Distance (http://en.wikipedia.org/wiki/Taxicab_geometry)? – Adriano Aug 07 '13 at 01:24
  • Are you finding the Pythagorean Theorem inefficient? Are these grids so massive you are running into problems squaring numbers, adding, and taking the square root? – Adrian Keister Aug 07 '13 at 02:13
  • It is a discrete layout algorithm that has a running time of n^3 so I wanted to see how I can improve it and it seemed like this type of calc. might have already been done. – mihajlv Aug 07 '13 at 11:08
  • @Adriano I need the euclidean distance using the only the cell's width's and heights. – mihajlv Aug 07 '13 at 11:12
  • How is your running time $\Theta(n^3)$? What does $n$ represent? I'd imagine that using the Pythagorean Theorem would have a constant running time of $\Theta(1)$, since all you need to do is look up the points' coordinates and compute: $$ \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} $$ – Adriano Aug 07 '13 at 16:56
  • @Adriano Right, it is a force directed algorithm n^2 to compute forces run m number of times ~ n^3 – mihajlv Aug 08 '13 at 14:37

0 Answers0