Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting

Non-dominated sorting arranges a set of points in n-dimensional Euclidean space into layers by repeatedly removing the coordinatewise minimal elements. It was recently shown that nondominated sorting of random points has a Hamilton-Jacobi equation continuum limit. The obvious numerical scheme for this PDE has a slow convergence rate of . In this paper, we introduce two new numerical schemes that have formal rates of O(h) and we prove the usual theoretical rates. We also present the results of numerical simulations illustrating the difference between the formal and theoretical rates.