Hamilton-Jacobi scaling limits of Pareto peeling in 2D

Abstract

Pareto hull peeling is a discrete algorithm, generalizing convex hull peeling, for sorting points in Euclidean space. We prove that Pareto peeling of a random point set in two dimensions has a scaling limit described by a first-order Hamilton-Jacobi equation and give an explicit formula for the limiting Hamiltonian, which is both non-coercive and non-convex. This contrasts with convex peeling, which converges to curvature flow. The proof involves direct geometric manipulations in the same spirit as Calder (2016).

arXiv comment60 pages, 24 figures; v3 includes additional exposition