2
$\begingroup$

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?

  • 0
    set equal this lines each other,did i guess correctly what did you mean?2012-03-24
  • 0
    I'm looking for algorithms to solve this problem in the most efficient way..2012-03-24
  • 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?2012-03-24
  • 0
    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.2012-03-24

1 Answers 1

1

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

  • 0
    Can the Graham's algorithm (http://en.wikipedia.org/wiki/Graham_scan) be extended to the case when points are added or removed?2012-03-27
  • 0
    This seems like a different question that might be more appropriate for cs.SE.2012-03-28