An Optimal Algorithm for the Maximum Three-Chain Problem
R. D. Lou, Majid Sarrafzadeh · SIAM Journal on Computing · 1993
Given a two-dimensional point set $\rho $, a chain C is a subset of $\rho $ in which for every two points one is dominated by the other. A k-chain is a subset of $\rho $ that can be partitioned into k-chains. The size of a k-chain is the total number of its points. A k-chain with maximum size, among all possible k-chains, is called a maximumk-chain. First geometric properties of k-chains are studied for an arbitrary k. Then a $\Theta (n\log n)$-time algorithm is presented for finding a maximum three-chain in a point set $\rho $, where $n = |\rho |$.