Я пытаюсь найти алгоритм, который найдет все пересечения набора линий и вычислит минимальный прямоугольник, который содержит все пересечения за O (n log n) времени. До сих пор я предполагаю, что это связано с двойственностью и выпуклыми оболочками, но я как бы застрял на том, как это на самом деле поможет мне решить эту проблему.

Если у кого-то есть идеи по этому поводу, пожалуйста, дайте мне знать. Спасибо :)