Fast algorithm to get the most outer points of multiple colinear points

Question

I have multiple unsorted 2D points P0, P1, P2, ..., Pn that all are colinear. I want to get as fast as possible the outer points *P_0* and *P_n* which have the biggest distance.

P0          P1       P2   P3                   Pn
|-----------|--------|----|--------------------|

I have no idea how to do it but with a brute force algorithm calculating all distances and than sorting the points. Any idea?

Answer 1

If the points are colinear, then you can compare them by comparing their coordinates directly. You don't need to calculate distance from origin or between points. And you don't need to sort the entire list to get the min and max.

Pseudo-code:

min = p0
max = p0
for each point p
    if p.X < min.X || p.Y < min.Y then min = p
    if p.X > max.X || p.Y > max.Y then max = p

You could fiddle with the algorithm somewhat: there's no need to check Y unless the X values are all identical.