Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
set equal this lines each other,did i guess correctly what did you mean? – dato Mar 24 '12 at 7:34
I'm looking for algorithms to solve this problem in the most efficient way.. – Bob Mar 24 '12 at 7:37
1  
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

up vote 1 down vote accepted

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

share|improve this answer
Can the Graham's algorithm (en.wikipedia.org/wiki/Graham_scan) be extended to the case when points are added or removed? – Bob 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.