AN OPTIMAL ALGORITHM FOR THE MAXIMUM 3-CHAIN PROBLEM

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 i s 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 siz e, among all possible k-chains, is called a maximum k-chain. First geo metric properties of k-chains are studied for an arbitrary k. Then a T HETA(n log n)-time algorithm is presented for finding a maximum three- chain in a point set rho, where n = Absolute value of rho.