 <p>No, you can not calculate the furthest point for each point in <code>O(n)</code>. The best you can obtain is <code>O(n log n)</code> with a <a href="https://en.wikipedia.org/wiki/K-d_tree" rel="nofollow">2-d tree</a>. You can do this with a technique, similar to finding a closest point.</p> <p>Read a more detailed <a href="http://stackoverflow.com/a/34864864/1090562">answer here</a> where I show a couple of other approaches to solve a similar problem.</p>