Finding the maximum pairwise difference in a collection of colors Note that this problem is equivalent to finding the longest line segment defined by any two points in a collection of 3D coordinates, which may be an easier way to visualize the problem, and is almost certainly a version that has received more research.

Essentially, given a List&lt;Color&gt; and this method...

public static int ColorDiff(Color a, Color b)
{
    int rDiff = a.R - b.R;
    int gDiff = a.G - b.G;
    int bDiff = a.B - b.B;
    return (int)Math.Sqrt(rDiff * rDiff + gDiff * gDiff + bDiff * bDiff);
}


... I'd like to get the highest ColorDiff value for any pair of points in the list.

Informed Sequential Approach

int max = 0;
for (int i = 0; i &lt; colors.Count - 1; i++)
{
    for (int j = i + 1; j &lt; colors.Count; j++)
    {
        int temp = ColorDiff(colors[i], colors[j]);
        if (temp &gt; max)
            max = temp;
    }
}


Naive LINQ Parallel Approach

int max = colors.AsParallel().Max(a =&gt; colors.Max(b =&gt; ColorDiff(a, b)));


Informed Parallel Approach

int max = 0;
Object locker = new Object();
System.Threading.Tasks.Parallel.For(0, colors.Count - 1, () =&gt; 0,
    (i, unused, localMax) =&gt;
    {
        int temp = 0;
        for (int j = i + 1; j &lt; colors.Count; j++)
            temp = Math.Max(temp, ColorDiff(colors[i], colors[j]));
        return Math.Max(localMax, temp);
    }, localMax =&gt;
    {
        lock (locker)
        {
            if (localMax &gt; max)
                max = localMax;
        }
    });


My testing indicates the naive LINQ approach takes about 60-70% of the time the sequential approach takes. However, I'm pretty sure it's naively doing the comparisons twice (ColorDiff(colors[i], colors[j]) and ColorDiff(colors[j], colors[i])), and that the speedup is entirely due to the parallelization across 4 cores. The performance of the informed parallel approach supports that; it takes approximately 30-40% of the time the LINQ approach takes, making it about 5 times faster than the informed sequential approach.

The LINQ approach is taking approximately 1 minute on my trial datasets (about 60 thousand elements in the list), and a little over 15 minutes on a larger dataset (230 thousand elements). I don't even want to know how long it will take on a full size dataset (about 1.1 million elements in the list).

Can I improve the brute force approach any further? Or better yet, is there an algorithm I can easily implement in C# that's better than O(n2)? A good approximation of the max value (within 5% of the true max) would probably be acceptable.

Extra information:


Because these are colors rather than points, their R, G, and B values are guaranteed to be in the range 0 to 255. I don't know if knowing the area the points will be inside helps, though; the way the colors are generated results in them often being clustered in a small sub-space of the total range.
Because of the way the colors are generated, every color will have N exact duplicates in the list (N >= 0, usually &lt; 4). The value of N will be known at this point, but the ordering of the list must be preserved and is not guaranteed to keep duplicates near each other. A shallow copy of the list can be made and ordered if that helps (and is worth the extra CPU time &amp; memory).
Ramos (2001) gives a \$O(n \log n)\$ algorithm, but the paper is not freely available, and apparently the algorithm is very complex. So take a look instead at Malandain and Boissonnat (2004) who give a simple algorithm that is \$O(n^2)\$ in the worst case, but apparently performs well for distributions found in practice.


E. A. Ramos (2001). "An Optimal Deterministic Algorithm for Computing the Diameter of a Three-Dimensional Point Set". Discrete and Computational Geometry, 26:2, pp. 233–244.
Grégoire Malandain and Jean-Daniel Boissonnat (2004). "Computing the Diameter of a Point Set". INRIA research report.