Maximize distance between points on a line

So lets say I have a certain duration of time starting at time(0) ranging to time(N). I also have a set of points whose values all exist within the range of values of that time frame.

I want to pick 4 points from that set that maximizes the distance between each point.

Just as an example say my range is 0-10 and I have points {1,2,4,5,7,9,10}. Ideally I would want to pick 1,4,7, and 10.

-
I suppose the quantity you want to maximize is $\min_{P,Q \in S} d(P,Q)$ where $S$ is the set of the points you chose. Is that correct? It looks a little unclear from the way you phrased it. –  Niccolò Sep 20 '12 at 18:41
Yes I believe that is correct, I apologize I'm still trying to clarify what I am looking for myself. –  Michael Sep 20 '12 at 18:44
This is a combinatorial optimization problem. Why the "linear programming" tag? –  Rod Carvalho Sep 20 '12 at 19:33
Sorry, didn't know what to tag it as, thought the optimization fell under linear programming –  Michael Sep 20 '12 at 20:18

1 Answer

The quick and dirty answer, which functions in most cases, is to simply divide the range by the number of points you need (here, $\dfrac{10}{4} = 2.5$) and then choose the point from the set that is closest to $2.5k$ where $k$ is the ordinal of the point being chosen. Assuming a sufficient number of evenly-distributed points within the range, this will produce an optimal answer, but there are distributions of points for which this won't work.

I'm reminded, whenever I hear of a "optimal path" problem like this, of Dijkstra's algorithm. We will consider a graph, consisting of the 7 numbers in the set, arranged as nodes connected by "one-way" paths (edges) leading from each smaller node to each larger number, having length equal to the difference between the numbers they connect (the node from 4 to 9 will have length 5). We can tell by inspection that we want to start at node 1 and end at node 10. We want a path, consisting of exactly four nodes (including 1 and 10, which means we can remove the paths from 1 to 9 and from 1 to 10 as they cannot be valid), that is not the shortest path (as all paths will have the same length), but the smallest absolute difference between paths.

To do this, the algorithm will consider the length of each path from the start to each adjacent nodes. It will remember the path it has traversed as both the "shortest" and "longest" path so far, and the "cost" to get to any accessible node from node 1 will be zero (the difference between longest and shortest so far). It will then pick one of these points, and consider all accessible paths from there. If the path is longer than the "longest" path, it becomes the new longest path; same goes if it's shorter then the "shortest" path. The cost to get to that node from the start node is the difference between the longest and shortest path traversed. One additional rule must be added; the algorithm will keep track of the number of nodes visited along a path, and when that number is 3 (including node 1) the only path it may consider from its current node is the path to node 10. Conversely, if the number of nodes visited is not 3, it may not consider the path to node 10 as an option.

The correct answer is the path with the lowest overall cost. As the algorithm recurses, it will find and remember the "cheapest" way to get to each node, and by the time it's done it will have found the cheapest way to reach node 10 given the stated rules.

-
You know, I was thinking a variation of Dijkstra's algorithm would do that trick. I have been using this linear programming engine at work, so I wanted to see if it was possible in that domain. I'm going to give some more thought to the graph approach and decide if it's the best way to go. Thanks! –  Michael Sep 20 '12 at 20:28