This part riiight here:
I don't think tables would be practical (800 * 600)^2 x1, y1, x2, y2 the distance from any point to any other = 2.304*10^11 values.
That's where interpolation comes in handy. The table need only contain crude known values, like 100, 105, 110, 120, etc. So that when a request for 103 comes in, it fakes the value by using its neighbors, 100 and 105. Same goes for a trig table, just wrap SIN() around each of the numbers I just used.
Not to mention the number of "values" might overcount. You want the number of pair-to-pair distances in a table? I think this is just a bunch of radii. Thats what I think i mean. Will have to look closer if not. Meh, take or leave this statement.