Numerical Schemes for the Hamilton-Jacobi Equation Continuum Limit of Non-dominated Sorting

Jeff Calder
Department of Mathematics, University of California, Berkeley

Non-dominated sorting arranges a set of points in n-dimensional Euclidean space into layers by repeatedly peeling away the coordinatewise minimal elements. It was recently shown that non-dominated sorting of random points has a Hamilton-Jacobi equation continuum limit. The obvious numerical scheme for this PDE has a slow convergence rate of $O(h^{1/n})$. In this talk, we introduce two new numerical schemes that have formal rates of $O(h)$ and we prove the usual $O(\sqrt{h})$ theoretical rates.