@techreport{Report-348-1993,
Title = {Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms},
Author = {Stefan Felsner and Lorenz Wernisch},
Booktitle = {Proceedings of the 25th Annual ACM Symposium on the Theory of Computing},
Pages = {146-153},
Year = {1993},
Number = {348},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
Abstract = {A chain of a set $P$ of $n$ points in the plane is a chain of the dominance order onĀ $P$. A $k$-chain is a subset $C$ of $P$ that can be covered by $k$ chains. A $k$-chain $C$ is a maximum $k$-chain if no other $k$-chain contains more elements than $C$. This paper deals with the problem of finding a maximum $k$-chain of $P$. Recently, Lou Sarrafzadeh and Lee proposed algorithms to compute maximum 2- and 3-chains in optimal time $O(n\log n)$. Using the 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\log n)$ using $O(kn)$ space. The basic idea is, that the canonical chain partition of a maximum $(k-1)$-chain in $S(P)$ provides $k$ regions in the plane, such that, a maximum $k$-chain for $P$ can be obtained as the union of maximal chains in these regions. If our theorems on skeletons are added to Viennot's results, they allow to derive the full Greene-Kleitman theory for permutations from properties of skeletons.}
}