Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane
Step 1. Sort all the points according to their $x$-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same $x$-coordinate. You can drop (or ignore in all subsequent steps) all the buckets, containing only single point.

Step 2. Define a mapping $M$, where the key will be a closed integer interval and the value - ordered set of integers. Scan all the buckets, created in the Step 1. For each bucket insert all the possible pairs of its $y$-coordinates into the mapping $M$ - their corresponding $x$-coordinates must be inserted into the set, corresponding to this interval:

function Insert(M, x, y0, y1)
  if mapping M contains element ([y0, y1] -&gt; S)
    insert x into set S
  else
    insert element ([y0, y1] -&gt; (x)) into mapping M


You can drop (or ignore in all subsequent steps) all the elements of the mapping $M$, for which their value set contains only a single number.

Step 3. The mapping M will contain elements like this:

$$([y_0, y_1] \rightarrow (x_0, x_1, ..., x_{m-1}))$$

The biggest rectangle with "vertical" side $[y_0, y_1]$ will have "horizontal" side $[x_0, x_{m-1}]$, so you can ignore all the middle elements of the ordered set. Finally, scan all the elements in the $M$ to find the element with largest rectangle area $A$:

$$A = (y_1 - y_0) \cdot (x_{m-1} - x_0) $$  

Number of intervals in $M$ is $O(n^2)$, so time to insert into the mapping will be $O(n^2log(n))$.