TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
Citation key Report-348-1993
Author Stefan Felsner and Lorenz Wernisch
Title of Book Proceedings of the 25th Annual ACM Symposium on the Theory of Computing
Pages 146-153
Year 1993
Number 348
Institution Technische Universität Berlin, Institut für 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łog 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łog 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.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe