# A Hamilton-Jacobi equation for the continuum limit of non-dominated sorting

arXiv: https://arxiv.org/abs/1302.5828 · HTML: https://mlsanity.com/paper/1302.5828/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2013.

## Built on by (most cited first, 3 of 3)

- [Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth](https://mlsanity.com/paper/2202.08789/) (2022)
- [Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applications](https://mlsanity.com/paper/2111.03217/) (2021)
- [Tukey Depths and Hamilton-Jacobi Differential Equations](https://mlsanity.com/paper/2104.01648/) (2021)

## Abstract (arXiv)

We show that non-dominated sorting of a sequence of i.i.d. random variables in Euclidean space has a continuum limit that corresponds to solving a Hamilton-Jacobi equation involving the probability density function of the random variables. Non-dominated sorting is a fundamental problem in multi-objective optimization, and is equivalent to finding the canonical antichain partition and to problems involving the longest chain among Euclidean points. As an application of this result, we show that non-dominated sorting is asymptotically stable under random perturbations in the data. We give a numerical scheme for computing the viscosity solution of this Hamilton-Jacobi equation and present some numerical simulations for various density functions.