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: wernisch@inf.fu-berlin.de
Report B 92-27
December 1992
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-92-27.ps.gz
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.