CODEWITHSUNDEEP
geometrycomputational-geometryintersectionsegment
Monica
Monica

Reputation: 51

Can this be solved with a line sweep algorithm in O(n)?

In this problem we are given n horizontal segments in the plane, find in O(n) time a line that intersects all the segments and has the largest possible slope, or determine that there is no such line.

I thought about finding all possible lines by having an inequality solving it and getting all possible line equations and then finding the one with the biggest slope however I can't find the solution is related to anything we learned in computational geometry Can anyone give me a hint or mention any related subject in computational geometry that could help

Upvotes: 5

Views: 379

Answers (2)

HEKTO
HEKTO

Reputation: 4191

No, this problem can't be solved by the line sweep algorithm in linear time - please see the @YvesDaoust comment. However, it can be solved in linear time by another method - please see below.

Your intent to describe intersections between n segments and the stabbing line by inequalities was correct, however you could go further and reduce your problem to a linear programming (LP) problem with two variables and 2*n constraints.

Let's denote parameters of a segment i by three numbers - xMin(i), xMax(i) and y(i). The stabbing line will be described by equation y = a*x + b. This line must intersect the segment i, so for each such segment we have two inequalities, guaranteeing the intersection:

a*xMin(i) + b <= y(i)
a*xMax(i) + b >= y(i)

So, you need to maximize the slope a subject to 2*n constraints above, and this is a well known fixed-dimension LP problem with two variables a and b. According to this paper by Nimrod Megiddo, LP problems with n constraints and fixed (non-depending on the n) number of variables can be solved in O(n) time.

Upvotes: 1

Spektre
Spektre

Reputation: 51913

As comments suggested line sweep algorithm is slower than O(n) so the answer is NO however simple O(n) approach is still possible for example like this:

  1. find BBOX of your intersection line

    so You are searching for x0,y0,x1,y1 coordinates of "inscribed" rectangle crossing the interior of all lines (aqua rectangle). This can be done in O(n)

    BBOX

    So search all lines and get:

    y0 = min(y)
y1 = max(y)
x0 = max(left_x)
x1 = min(righ_x)

    where left_x<right_x are the two x coordinates of each line.

  2. construct your line

    In case the x0>x1 there is no such line possible.

    For smallest slope simply use one of the diagonals of the BBOX:

    Line(x0,y0,x1,y1)
Line(x0,y1,x1,y0)

    diagonal

    which depends on your coordinate system (points might be even reversed)...

    The biggest slope is vertical line so you can use any x inside <x0,x1> interval for example

    Line(x0,y0,x0,y1)

    vertical line

Upvotes: 0

Related Questions