For low dimensions, it might be useful to look at the convex properties of the Pareto front. If a point P is on Pareto front, it is not in the interior of the convex hull of undominated points. In two dimensions, one can compute the convex hull of N points in O(N log N) time. This typically allows for faster Pareto front computation, but not in the worst case.