2

I'm struggling with a problem of Lecture on discrete geometry by Matusek.

Given $C\subset\mathbb{R}^{d}$ a compact and convex set and $p$ an interior point of $C$, it asks to prove the existence of a line $\ell$ passing through $p$ such that the segment $\ell\cap C$ is at least as long as any segment parallel to $\ell$ and contained in $C$.

Actually this was posted before but the solution given was based on unit vector fields on $S^{n}$.

The idea of the proof is to find parallel supporting hyperplanes of $C$ with endpoints $x,y$ such that the segment $[x,y]$ passes through $p$ and this will give the desire line. Nevertheless, I don't know how to start looking for those hyperplanes.

The book post this exercise after the separation theorem and Carathéodory theorem so I guess this theorems are sufficient to prove the above result.

Thank you in advance :)

Yeipi
  • 513
  • I would suspect that this needs more than separation and a representation theorem to prove. – copper.hat Nov 06 '23 at 04:50
  • What do you suspect to prove it? – Yeipi Nov 06 '23 at 14:06
  • On the other solution, the "supporting hyperplanes" are tangent hyperplanes to $\partial C_\epsilon$, where $C_\epsilon$ consists of all points within $\epsilon$ of $C$. The reason for this extension is that $C$ itself may not have a smooth boundary, so the tangent planes may not exist for it. For any line through $p$, it must intersect $C_\epsilon$ in a line segment. $x$ and $y$ are the endpoints of that segment. I.e., they lay on the boundary. The solution uses a homotopy result to show that some line has to have the tangent planes at $x$ and $y$ parallel. – Paul Sinclair Nov 06 '23 at 23:22
  • Couldn't it be a more elementary proof without fancy homotopy theory? – Yeipi Nov 06 '23 at 23:46
  • I am just explaining certain details of the other thread, not even suggesting it is correct. Since I posted that comment, I've been trying to trace back why finding these parallel planes shows that this direction means the line segment through $p$ is maximal for all parallel line segments, but have not yet spotted it. Has the book already covered Borsuk-Ulam? It seems to me a direct appeal to that theorem is likely to be sufficient. – Paul Sinclair Nov 07 '23 at 00:06
  • Yeap, I tried to use Borsuk-Ulam but I don't know how to apply it and the book does not already cover it as the moment it presents the exercise. Actually is the first chapter just after separation theorem and Carathéodory theorem. But I guess is not illegal to apply Borsuk-Ulam – Yeipi Nov 07 '23 at 16:45

1 Answers1

1

Here is a proof that I believe works:

First translate the problem so that $p = 0$.

For each direction $v \in S^{d-1}$, consider the line of $v$. Define $f_d(v)$ to be the length of the line segment intersecting $C$ of that line, minus the maximum length of all such line segments parallel to $v$. By compactness of $C, f_d$ is well-defined. By the convexity of $C, f_d$ should be continuous, but I'll leave confirming that up to you. Since $v$ and $-v$ are parallel, $f_d(-v) = f_d(v)$.

Let $\{e_i\}_{i=1}^d$ be the canonical basis for $\Bbb R^d$ and consider the function $$g_d(v) = f_d(v)v\cdot e_d$$ Clearly $g_d$ is also continuous and $g_d(-v) = -g_d(v)$ for all $v$. By the intermediate value theorem, there must be a $v$ for which $g_d(v) = 0$. That means either $f_d(v) = 0$ or $v$ is orthogonal to $e_d$. In the first case, we are done. $v$ is the direction making the line segment through $0$ the longest of all parallel segments.

If $f_d(v) \ne 0$, then $v$ is orthogonal to $e_d$, we intersect $C$ with the hyperplane perpendicular to $e_d$ and apply the canonical isometry of $\Bbb R^{d-1}\times \{0\}$ with $\Bbb R^{d-1}$ to get a compact convex set $C_{d-1}$ with $0$ in its interior, and end up with the same problem one dimension lower. Applying the same logic, we either get a vector for which $f_{d-1}$ is $0$, thus giving us a solution of this new problem, or else $v$ is orthogonal to $e_{d-1}$, and we reduce to that subspace. Note that $f_{d-1}(v) = f_d((v, 0))$ for all $v \in S^{d-2}$.

If this continues all the way down to $C_1$ in $\Bbb R^1$, then $v\in S^0$ is either $1$ or $-1$ and $v\cdot e_1 = \pm 1 \ne 0$. So there $f_1(v) = 0$ is true. In all cases, there is some $1 \le k \le d$ and some $v_k\in S^{k-1}$ with $f_k(v_k) = 0$, and therefore $f_d(v) = 0$ for $v = (v_k,0,\dots,0)$. Thus we have the desired result.

Paul Sinclair
  • 43,643