¿Cómo encontrar una línea que apuñale el máximo número posible de segmentos?

Question

Supongamos que nos dan $N$ segmentos de ángulos diferentes y arbitrarios en el plano que son disjuntos, y queremos encontrar una recta que apuñale el máximo número de segmentos. ¿Cómo hacer esto? He pensado en los árboles de cuadratura pero no parece que sirva de nada...

Answer 1

Esto debería ayudar:

Edelsbrunner, Herbert, Hermann A. Maurer, Franco P. Preparata, Arnold L. Rosenberg, Emo Welzl y Derick Wood. "Segmentos de línea de apuñalamiento". BIT Matemáticas Numéricas 22, no. 3 (1982): 274-281. ( Descarga del PDF .)

dualizan los segmentos de línea a cuñas dobles y utilizan esa representación para sus algoritmos.

---

         

---