MAXIMUM K-CHAINS IN PLANAR POINT SETS - COMBINATORIAL STRUCTURE AND ALGORITHMS

A chain of a set P of n points in the plane is a chain of the dominanc e order on P. A k-chain is a subset C of P that can be covered by k ch ains. A k-chain C is a maximum k-chain if no other k-chain contains mo re elements than C. This paper deals with the problem of finding a max imum k-chain of P in the cardinality and in the weighted case. Using t he skeleton S(P) of a point set P introduced by Viennot we describe a fairly simple algorithm that computes maximum k-chains in time O(kn lo g n) and linear space. The basic idea is that the canonical chain part ition of a maximum (k - 1)-chain in the skeleton S(P) provides k regio ns in the plane such that a maximum k-chain for P can be obtained as t he union of a maximal chain from each of these regions. By the symmetr y between chains and antichains in the dominance order we may use the algorithm for maximum k-chains to compute maximum k-antichains for pla nar points in time O(kn log n). However, for large k one can do better . We describe an algorithm computing maximum k-antichains (and, by sym metry, k-chains) in time O((n(2)/k) log n) and linear space. Consequen tly, a maximum k-chain can be computed in time O(n(3/2) log n) for arb itrary k. The background for the algorithms is a geometric approach to the Greene-Kleitman theory for permutations. We include a skeleton-ba sed exposition of this theory and give some hints on connections with the theory of Young tableaux. The concept of the skeleton of a planar point set is extended to the case of a weighted point set. This extens ion allows to compute maximum weighted k-chains with an algorithm that is similar to the algorithm for the cardinality case. The time and sp ace requirements of the algorithm for weighted k-chains are O(2(k) n l og(2(k) n)) and O(2(k) n), respectively.