Metric Geometry – Vertical Line Intersections with Non-Parallel Lines

discrete geometryincidence-geometrymg.metric-geometry

Pick $n\ge 3$ non-vertical lines $\mathscr{L}:=\{\ell_1,\ldots,\ell_n\}$ in the plane which are pairwise non-parallel, and they are not all concurrent in a single point.

Question. Does there exist a vertical line $L$ which has $n-1$ or $n-2$ intersections with $\mathscr{L}$?

Note: More explicitly, "$L$ has $k$ intersections with $\mathscr{L}$" means that the set $\{L\cap \ell_i: i=1,\ldots,n\}$ has $k$ distinct points.

Partial note 1: By using a dual result due to Ungar here one can see that there are at least $n-1$ vertical lines $L$ which have at most $n-1$ intersections with $\mathscr{L}$

Partial note 2: The Sylvester-Gallai problem shows the existence of an ordinary line, that is, given $n$ points in the plane, the exists a connecting line passing through exactly two of those points (this has been improved "optimally" here by Green and Tao). In the setting above, dually, there exists a point which is the intersection of exactly two lines of $\mathscr{L}$.

Partial note 3: This seems to be somehow related to (dual of) Problem 1 at the end of this article, as suggested by domotorp in his answer at this previous question. However, the motivation of the latter problem was a conjecture of Erdos and Purdy, namely, $n$ points in the plane determine at least $\lfloor (n-1)/2\rfloor$ triangles with distinct positive area; finally, this has been proved by Pinchasi in 2008 here.

Best Answer

For the solution see the attached figure here. It is the counterexample with $n=8$. Vertical lines represent all possible vertical lines which have less that $n$ intersection points with given lines.

How I found this counterexample?

By duality of the real projective plane, the problem is equivalent to the following:

Given $n$ distinct points on the plane such that they are not collinear and no two of them lie on the vertical line, is it true that there exists a direction $\mathcal{D}$ such that when passing a line from $\mathcal{D}$ through every given point we obtain $n-1$ or $n-2$ distinct lines?

And the answer is no. The counterexample consists of the vertices of the regular octagon rotated so that no two vertices lie on the vertical line. The figure corresponds to such octagon.

More notes. After the discussion with my colleagues from Katowice we concluded a little more about the problem.

Concerning the equivalent (dual) problem, given a set of $n$ points on the plane, we may consider the set $I$ of all natural numbers $j$ such that there exists a direction $\mathcal{D}$ yielding exactly $j$ distinct lines (when passing a line from $\mathcal{D}$ through every given point).

For a regular polygon with $n=2k$ vertices we have $I=\{k,k+1,2k\}$ and for a regular polygon with $n=2k+1$ vertices we have $I=\{k+1,2k+1\}$. Therefore $n=7$ is sufficient for a counterexample to the original problem.

One more observation is that transforming a regular polygon through an affine bijection of $\mathbb{R}^2$ preserves parallel lines, so the image of $n$ points under such transformation has the same set $I$ as the original points.

Related Question