Maximum $k$-Chains in Planar Point Sets: Combinatorial Structure and Algorithms

Lorenz Wernisch (joint work with Stefan Felsner) Institut für Informatik Freie Universität Berlin email: Report B 92-27 December 1992

Get the report here or by anonymous ftp: 
File:   pub/reports/
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 {\it 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, Sarrafzadeh, Lou, and Lee~\cite{SarrafzadehLouLee90,SarrafzadehLou92} 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~\cite{Viennot77,Viennot84} we describe a fairly simple algorithm that computes maximum k-chains in time $O(kn\log n)$ using $O(kn)$ space. \comment{ 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. To prove the correctness of the algorithm we need some theorems on skeletons.} 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.