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 quadratic in n. 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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.