Rom Pinchasi and Günter Rote:
On the maximum size of an anti-chain of linearly separable sets and
convex pseudo-discs
Israel Journal of
Mathematics 172 (2009), 337–348.
doi:10.1007/s11856-009-0076-z,
arXiv:0707.0311 [math.MG].
Abstract
We show that the maximum cardinality of an anti-chain composed of
intersections of a given set of n points in the plane with
half-planes
is close to n2. We approach this problem by
establishing the
equivalence with the problem of the maximum monotone path in an
arrangement
of n lines. For a related problem on antichains in families of
convex
pseudo-discs we can establish the precise asymptotic bound: it is
quadratic in
n. The sets in such a family are characterized as intersections
of a
given set of n points with convex sets, such that the
difference
between the convex hulls of any two sets is nonempty and connected.
Last update: September 1, 2009.