TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel


zur Navigation

Preprints 1993

Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
Zitatschlüssel Report-348-1993
Autor Stefan Felsner and Lorenz Wernisch
Buchtitel Proceedings of the 25th Annual ACM Symposium on the Theory of Computing
Seiten 146-153
Jahr 1993
Nummer 348
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe