I am trying to come up with an algorithm that can take a set of colors X and return a new set of colors X' that consists of only contrasting colors from the original set X. In other words I want to filter out similar colors from the passed in color set. If you would like to think in terms of color differencing, the problem can be thought of filtering out all colors that are <= some distance k from any color in the set.
Does anyone know of a way to do this in linear time or O(N). I am ok with other time complexities as well as long as it is not O(N^2), every solution I come up with takes polynomial time. I tried reducing the problem to the famous "find all pairs of integers in an array that sum to K" but that reduction did not work. I am using the deltaE metric to determine how far apart or dissimilar/contrasting two colors are.
Use a cover tree to store colors under the ∆E metric. For each color, do an O(log n)-time proximity search in the cover tree and reject it if the nearest color is too close.