Bhattacharya 等人在 Computing Shortest Transversals of Sets 中给出了一个 $O(n\log n)$ 算法，但只证明了线段版本的最优性，没有给出直线版本的非平凡下界而是把它留作 Open Problem。
我尝试着把这个问题规约到单位圆上的 $\mathsf{MAXGAP}$ 问题（下面简称 $\mathsf{CMG}$，这里的 gap 定义为环上相邻两点的欧氏距离），GPT 告诉我可以这么做：
首先转化成判定问题，给定直线集 $H$ 判断最优解 $\mathsf{OPT}(H)$ 是否满足 $\mathsf{OPT}(H)\leq L$。
给定单位向量集合 $U=\{u_1,\dots,u_n\}\subset S^1$，对每个 $u_i$ 构造两条平行切线 $u_i\cdot x=1$ 和 $u_i\cdot x=-1$。设 transversal segment 的位移向量为 $v$。它同时穿过这两条边界线当且仅当 $|u_i\cdot v|\ge 2$ 对所有 $i$ 成立。此时答案只跟方向有关，只需要判断 $$ L\geq \frac{2}{\max_{\|w\|=1}\min_{i} |u_i\cdot w|} $$
固定 $w$，令 $z\perp w$。由于 $|u_i\cdot w|$ 等于 $u_i$ 到 $\pm z$ 较小夹角的正弦，因此问题等价于在圆上选一个方向 $z$，使它离 $Q=U\cup(-U)$ 中最近的点尽可能远。显然最优的 $z$ 是 $Q$ 中最大相邻角度间隔的中点。若该间隔为 $\theta$ 则最近角距离为 $\theta/2$，所以 $\max_{\|w\|=1}\min_{i} |u_i\cdot w|=\sin(\theta/2)$。
于是 $\mathsf{OPT}(H)=\frac{2}{\sin(\theta/2)}$。若 $D(Q)$ 表示 $Q$ 中相邻点的最大欧氏距离，则 $D(Q)=2\sin(\theta/2)$，因此 $\mathsf{OPT}(H)=\frac{4}{D(Q)}$。判定问题 $\mathsf{OPT}(H)\le L$ 等价于 $D(Q)\ge 4/L$。
但是到这里还没完，注意到 $Q$ 的结构比较特殊（对称点都在集合里），我们还得说明这种特殊情况的求解不比一般情况简单。一种可行的思路是：
对于任意的 $\textsf{CMG}$ 实例，把所有角度 $/2$ 再复制一遍到下半圆 $$ \{\alpha_1,\dots,\alpha_n\} \mapsto \{\alpha_1/2,\dots,\alpha_n/2,\alpha_1/2+\pi,\dots,\alpha_n/2+\pi\} $$
如果这个新的实例能够求解，那么得到的答案可以转化成原先实例的答案
能够转化是因为：把角度当作 gap 答案的关系就是简单的 $/2$，在 $[0,\pi]$ 范围内角度关于弦长是单调的；而 $>\pi$ 的情况一定会支配答案所以没影响。
所以如果 $\mathsf{CMG}$ 在 algebraic computation-tree model 下具有 $\Omega(n\log n)$ 下界，那么本题也有 $\Omega(n\log n)$ 下界。
$\mathsf{CMG}$ 的下界证明只在一个未发表的 technical report 上出现过，并不是正式发表论文。
V. Sacristán, “Lower Bounds for Some Geometric Problems,” Technical Report MA-IR-98-0034, Universitat Politècnica de Catalunya, Departament de Matemàtica Aplicada II, 1998; revised June 1999. Author publication page: https://dccg.upc.edu/people/vera/research/pub/ PDF: https://dccg.upc.edu/people/vera/wp-content/uploads/2012/03/cotasnuevas.pdf
在正式论文中能够找到的可靠的下界要求点只能在第一象限内，而不是完整圆周。
D. T. Lee and Y. F. Wu, “Geometric Complexity of Some Location Problems,” Algorithmica 1 (1986), 193–211. DOI: https://doi.org/10.1007/BF01840442
