# 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

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.