Efficient removal of points with smallest crowding distance in two-dimensional incremental non-dominated sorting

Many evolutionary multi-objective algorithms rely heavily on non-dominated sorting, the procedure of assigning ranks to individuals according to Pareto domination relation. The steady-state versions of these algorithms need efficient implementations of incremental non-dominated sorting, an algorithm or data structure which supports efficient addition of a new individual and deletion of the worst individual. Recent research brought new advanced algorithms, but none of them can be cheaply adapted to sublinear location of the point having the smallest crowding distance, a measure used in the NSGA-II algorithm. In this paper we address this issue by reducing it to a series of extreme point queries to certain convex polygons. We present theoretical estimation of the worst-case running time, as well as experimental results which show that the proposed modifications reduce the running time significantly on benchmark problems for large population sizes.