Lorenz Wernisch

SODA Conference 1997 Conference Paper

Markov Chains for Linear Extensions, the Two-Dimensional Case

• Stefan Felsner
• Lorenz Wernisch

STOC Conference 1993 Conference Paper

Maximum k-chains in planar point sets: combinatorial structure and algorithms

• Stefan Felsner
• Lorenz Wernisch

FOCS Conference 1991 Conference Paper

Discrepancy and epsilon-approximations for bounded VC-dimension

• Jirí Matousek 0001
• Emo Welzl
• Lorenz Wernisch

Let (X, R) be a set system on an n-point set X. For a two-coloring on X, its discrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in R. It is shown that if for any m-point subset Y contained in X the number of distinct subsets induced by R on Y is bounded by O(m/sup d/) for a fixed integer d is a coloring with discrepancy bounded by O(n/sup 1/2-1/2d/ (log n)/sup 1+1/2d/). Also, if any subcollection of m sets of R partitions the points into at most O(m/sup d/) classes, then there is a coloring with discrepancy at most O(n/sup 1/2-1/2d/ n). These bounds imply improved upper bounds on the size of in -approximations for (X, R). All of the bounds are tight up to polylogarithmic factors in the worst case. The results allow the generalization of several results of J. Beck (1984) bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure. >