11

This has been bugging me for about two weeks now..

I have a cartesian plane with n number of points randomly placed on it. You can get the coordinates of each point. Now, how do you calculate the shortest distance to connect all of them. ie. A to D to C to F to B to E?

I have asked my Highschool Math Teacher, she simply replied, "You would use common sense."

I want to calculate it mathematically... Any ideas?

Rijnhardt
  • 213

2 Answers2

10

This really isn't a shortest-path problem per se, since you're not just finding the shortest path between a pair of vertices, but it is a graph theory problem. It is most emphatically not solvable by "common sense".

If you don't have to connect the points in a chain, (e.g. you are allowed to connect A,B,C,D by connecting A to each of the other three) then this is a minimum spanning tree problem, and can be solved by Prim's Algorithm (http://en.wikipedia.org/wiki/Prim%27s_algorithm) or Kruskal's Algorithm (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm) efficiently. If not, this is a special case of the Travelling Salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem) which is computationally difficult.

Unless you know something special about how the points are chosen, you probably aren't going to get out of computing most of the $\binom{n}{2}$ distances between them.

universalset
  • 8,269
  • 20
  • 33
  • 1
    You're right - this is the travelling salesman problem. I overlooked this in my answer. – Newb Nov 26 '13 at 13:18
  • @Newb. Thank you sir, for all the effort you put into the explanation.. I thoroughly enjoyed reading and admiring the effort you put into the drawings.. – Rijnhardt Nov 26 '13 at 14:42
  • Thanks.. I will upvote all of the comments as soon as I have 15 credits on the site.. Thanks again :) – Rijnhardt Nov 26 '13 at 14:43
5

Your Math Teacher's response is unsatisfactory, because in research, "common sense" will not lead you to some of the more unintuitive results. Your problem is actually quite meaningful: it is a version of the Shortest Path Problem.

Your problem is analogous to the Shortest Path Problem because if you have $n$ points on a Cartesian Plane and you want to find the shortest path to connect all of them, then that is analogous to having a complete graph with $n$ vertices, and wanting to choose the set of edges such that the graph is connected, but the sum of the edge weights is minimized. In this problem, the edge weight is just the distance between two points. There are many interesting solutions to the Shortest Path Problem - you should take a look at them.

So let's take a look at the "common sense" solution: the simplest intuitive algorithmic solution would be to start at any given point $(x_1,y_1)$, find the nearest $(x_b,y_b)$, connect those with a line, and then connect $(x_b,y_b)$ to its nearest neighbour, etc., until you are done. Here is a counterexample in which this algorithm fails. On the upper diagram, we start at $a$, on the lower diagram, we start at $d$:
enter image description here

The algorithm fails in this instance because the selection of the starting point matters. It is clearly not arbitrary - in this example, if we start at $a$ rather than at $d$, we get different 'shortest path' lengths.

So what's a working algorithm in terms of Euclidian Geometry that will always solve this problem? I'm not so sure, especially given considerations of time-complexity for large $n$. However, any algorithm capable of solving the Shortest-Path Problem should be able to do it.

Newb
  • 17,672
  • 13
  • 67
  • 114
  • Wouldn't that be a very, very extensive and tedious process as n gets bigger? I was thinking that.. (Using Analytical Geometry - Distance formula) But was thrown off by the idea of brute forcing the calculation... Thanks for the reading material. Will go through it soon.. – Rijnhardt Nov 26 '13 at 12:29
  • Here's one counterexample on the real line. Our points are positioned at -1, 0, 1/2, 1, 2, 3, 4 ... 10. Starting at zero the naive algorithm moves to right then has to double back to hit the point at -1 for a total distance of 21. – in_mathematica_we_trust Nov 26 '13 at 12:32
  • I didn't see your comments. I ran into a similar problem with the 'common sense' approach (i.e. thought of a counterexample) and have updated my answer since. – Newb Nov 26 '13 at 12:47
  • It only makes sense that you would have n^n possible solutions.. Wouldn't you? – Rijnhardt Nov 26 '13 at 12:48
  • @Rijnhardt no. If you have $n$ vertices and all of them are connected, then the first vertex has $n-1$ edges connecting it to $n-1$ vertices. The second vertex is also connected to $n-1$ vertices, but we've already seen the edge that connects it to the first vertex, so it has only $n-2$ "new" edges, etc. When we get to the very last vertex, we'll already have "seen" all of its edges. I think you would therefore have $n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 1 = n!$ solutions. – Newb Nov 26 '13 at 12:51
  • I know its kind of late, but the way you drew your sketch, the path D->A->C->B->E is actual the shortest path (assuming the distance AD > AB). – Dorian Feb 07 '20 at 16:34