2

Let $S$ be a set of $n$ lines in the plane and $I$ the set of their intersections. That is $I = \{(x,y)\in \mathbb{R}^2; (x,y)=s \cap r, \text{where } s,r \in S\}$. The task is to compute the bounding box of $I$ in $O(n\log(n))$. So to find the smallest rectangle parallel to coordinate axis that has $I$ in its interior.

I started by sorting the lines by their slope and figuring only the first and last intersection of a line with other lines are of interest. I suppose I need one more idea to make a solution out of it.

Zan
  • 157
  • 1
    Maybe explore: Brown, Kevin Q. "Fast Intersection of Half Spaces." No. CMU-CS-78-129. CMU, 1978. – Joseph O'Rourke Jun 02 '19 at 23:44
  • Thank you, I don't think it shows the solution but it gave me the idea which I wrote down as the answer to my question. – Zan Jun 03 '19 at 12:03

1 Answers1

3

The trick is in looking at the dual of the $n$ given lines.

A line $y=ax-b$ is represented with a point $(a,b)$ in the dual space. One can check somewhere on the web that it's possible to compute the convex hull of $n$ points in $O(n\log(n))$. So we do just that. Then notice that edges of the convex hull imply lines (just extend the edges - or segment - on both ends to infinity).

Then we go back to primal space by converting those lines to points. These points are a subset of all the intersections of the given $n$ lines. Note that the convex hull of $n$ points can have at most $n$ edges, therefore we look among at most $n$ intersections for the extremal values that give us the bounding box we wanted to find.

Note: there should be a way of finding the bounding box without going to the dual space and computing the convex hull.

Zan
  • 157