show/hide this revision's text 6 added a better upper bound on the VC-dimension

If I understand the question correctly, a subset $l$ of lines belongs to $S$ if and only if there is a straight-line segment crossing exactly the lines from $l$.

The problem is then equivalent to the following dual version:

What is the maximum VC-dimension of a finite set of points in the plane, with respect to the double-wedges that do not contain the origin?

Where by "double-wedge" I mean the union of two opposite regions of the plane between two crossing lines.

It is easy to see that a set of $6$ points in convex position cannot be shattered. Since every set of $17$ points in convex position contains a convex $6$-gon, the VC-dimension is at most 16.

The next step could be investigating all configurations of $6$ points plus the origin if there is some configuration that can be shattered.

[The answer was edited after Gjergji's comment.]


One can, indeed, show that the VC-dimension is at most $10$ by a counting argument outlined by Gjergji. A pair of faces containing the endpoints of the segment determines the subset $l$. For lines in general position, there are $${1+{n+1 \choose 2} \choose 2}$$ pairs of faces, which is still more than $2^n-1$ for $n=11$. But some of the subsets $l$ were overcounted: every $1$-element set was counted $n-1$ times and every $2$-element set at least twice, so we can subtract $3/2 \cdot n(n-1)$. In this way, we get an upper bound $2046$ for the number of subsets $l$ for $n=11$, which is just enough to show that the VC-dimension is at most $10$. Further improvements are possible, for example by considering overcounted triples or by considering the faces with more than $3$ vertices (using this result).


Edit: According to P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Chapter 8.2 or MathSciNet, MR1274574, Harbort and Moller [1] proved that every simple arrangement of $9$ pseudolines in the projective plane contains a subarrangement of six pseudolines with a hexagonal face. No such arrangement can be shattered: a triple of pseudolines determined by every other edge of the hexagonal face cannot be crossed by a pseudosegment that avoids the other three pseudolines. This shows that the VC-dimension is at most $8$, even in the stronger setting of pseudolines in the projective plane.

[1]: H. Harbort and M. Moller, Esther Klein problem in projective plane, J. Combin. Math. Combin. Comput. 15 (1994), 171--179.

show/hide this revision's text 5 improved upper bound

[The upper bound answer was edited after Gjergji's comment.]

One canbe improved as follows. In the original formulation of the problem, let indeed, show that the VC-dimension is at most $s$ be a segment crossing 10$ by a subset of linescounting argument outlined by Gjergji.Then the first and the last edge A pair of faces containing the arrangement endpoints of $L$ that are crossed by $s$ determine the segment determines the subset $l$ of lines crossed by $l$. There For lines in general position, there are at most $n^2 + n^2 (n^2-n) / 2$ such ${1+{n+1 \choose 2} \choose 2}$$pairs of edges. Thus if a set faces, which is still more than $2^n-1$ for $n=11$. But some of the subsets $n$ lines is shatteredl$ were overcounted: every $1$-element set was counted $n-1$ times and every $2$-element set at least twice, so we have can subtract $n^2 + n^2 (n^2-n) / 2 3/2 \ge 2^n - 1$cdot n(n-1)$. This inequality is not satisfied In this way, we get an upper bound $2046$ for the number of subsets $l$ for $n\ge 15$, hence n=11$, which is just enough to show that the VC-dimension is at most $14$.

This proof was inspired 10$. Further improvements are possible, for example by some ideas from considering overcounted triples or by considering the following paper:C. Dangelmayr, S. Felsner and W. T. Trotter, Intersection Graphs of Pseudosegments: Chordal Graphs, Journal of Graph Algorithms and Applications 14, nofaces with more than $3$ vertices (using this result).1, 5-17, 2010

[The answer was edited after Gjergji's comment.]

show/hide this revision's text 4 deleted 333 characters in body

If I understand the question correctly, a subset $l$ of lines belongs to $S$ if and only if there is a straight-line segment crossing exactly the lines from $l$.

The problem is then equivalent to the following dual version:

What is the maximum VC-dimension of a finite set of points in the plane, with respect to the double-wedges that do not contain the origin?

Where by "double-wedge" I mean the union of two opposite regions of the plane between two crossing lines.

Note that this formulation implies that in this case, "shattering" and "distinguishing" coincide.

It is easy to see that a set of $6$ points in convex position cannot be shattered. Since every set of $17$ points in convex position contains a convex $6$-gon, the VC-dimension is at most 16.

Regarding the lower bound, it is easy to see that every set of $5$ points can

The next step could be shattered. Moreover, there is a set investigating all configurations of $6$ points that can be shattered, too: for example, take the vertices of a regular pentagon and the center of plus the pentagon.

It origin if there is possible some configuration that larger shattered sets can still be found easily. It may also be possible to solve the question completely by inspecting small configurations of points by a complete case-analysisshattered.

EDIT:

The upper bound can be improved as follows. In the original formulation of the problem, let $s$ be a segment crossing a subset of lines. Then the first and the last edge of the arrangement of $L$ that are crossed by $s$ determine the subset $l$ of lines crossed by $l$. There are at most $n^2 + n^2 (n^2-n) / 2$ such pairs of edges. Thus if a set of $n$ lines is shattered, we have $n^2 + n^2 (n^2-n) / 2 \ge 2^n - 1$. This inequality is not satisfied for $n\ge 15$, hence the VC-dimension is at most $14$.

This proof was inspired by some ideas from the following paper: C. Dangelmayr, S. Felsner and W. T. Trotter, Intersection Graphs of Pseudosegments: Chordal Graphs, Journal of Graph Algorithms and Applications 14, no. 1, 5-17, 2010

[The answer was edited after Gjergji's comment.]

show/hide this revision's text 3 added a better upper bound
    Post Undeleted by Jan Kyncl
show/hide this revision's text 2 previous answer was wrong
    Post Deleted by Jan Kyncl
show/hide this revision's text 1