# Finding the intersections of straight lines

Given a set of lines intersecting the quadrant with $x, y>0$, what are the available algorithms for finding the area below all straight lines (including $y$ and $x$ axis)? In other words, methods to find the points of the polygon given be the intersections of the lines?

-
set equal this lines each other,did i guess correctly what did you mean? – dato datuashvili Mar 24 '12 at 7:34
I'm looking for algorithms to solve this problem in the most efficient way.. – ACAC Mar 24 '12 at 7:37
are you trying to find the area bounded by a set of lines and the x and y axes? by x,y > 0 do you mean that the x and y intercept of all lines in the set are positive? – Ben Mar 24 '12 at 8:17
The question is very confusingly written. I think you are interested in the area of a polygon given in the form $Ax\le b$, $x\ge 0$, which you can do with fast convex hull algorithms. – Louis Mar 24 '12 at 15:45

## 1 Answer

If I understand the question, you can compute the polygon you are interested in by dualizing, computing the convex hull, and then going back. This is pretty standard course material, e.g., http://www.cs.umd.edu/class/spring2012/cmsc754/Lects/lect08.pdf

-
Can the Graham's algorithm (en.wikipedia.org/wiki/Graham_scan) be extended to the case when points are added or removed? – ACAC Mar 27 '12 at 21:30
This seems like a different question that might be more appropriate for cs.SE. – Louis Mar 28 '12 at 9:56