this can be sped up using integer sorting algorithms, to have the same asymptotic running time as the sorting algorithms.

Three dimensions

For points in three dimensions, it is again possible to find the maximal points in time using an algorithm similar to the two-dimensional one that performs the following steps:
*Sort the points in one of the coordinate dimensions (the -coordinate, say)
*For each point, in decreasing order by -coordinate, test whether its projection onto the

1.Previous
3.Next