line-segment ordering; need algorithm
sflts1
I am looking for an algorithm (or algorithms) for a certain problem
involving line segments. I hope this is the right group for posting
this kind of request. If not, could someone suggest a better group?
I have a set of n line segments in the xy-plane. I know the endpoints
of each line segment. In fact, for each line segment, the x-
coordinates of the endpoints are the same. As such, line segment i can
be specified by end-points (x1, y1(i)) and (x2, y2(i)). I assume x2 >
x1. (Hence, none of the line segments are vertical, but some may be
horizontal.) Let the line describing segment i be given by y(i) = a(i)
x + b(i). For a given value of x, say x0, where x1 < x0 < x2, I want
to know the indices of the k lines having the largest y values from
these n line segments. Say, for example n = 6, k = 3 and for some
value of x0 the following holds:
a(3)x0+b(3) >= a(5)x0+b(5) >= a(2)x0+b(2) >= a(6)x0+b(6) >= a(1)
x0+b(1) >= a(4)x0+b(4)
For this x0, I want an algorithm that returns 3, 5, and 2.
Some more specifics …
1. For a set of n line segments, the operation of finding the k-
largest line segments must be repeated many times for different x
values. The x values are not known in advance.
2. k is roughly n/2.
3. n is at least 10, but it can be in the thousands.
As I only know some basics of data structures, the only idea I could
think of was the following. I maintain a k-item heap, containing the
k largest y-values currently computed. The following loop is
computed:
for each line segment i
1. Compute the y value from the line segment: y(i) = a(i)x0 + b(i).
2. If y(i) is larger than the smallest y-value in the heap, then add
pair (y(i), i) to the heap.
end for
Step A is an O(1) operation. As the heap size is k, then B takes at
most O(lg k) operations. Since A and B are repeated for each line
segment, the whole loop takes O(n lg k) operations. Can I do any
better?
I am looking for algorithms and/or data structures that could be of
help in this problem. References to papers or books are welcome.
Much thanks.
Elmar Sack
Sounds to be a linear programming problem, solvable in O(n) time. Look at
"LINEAR-TIME ALGORITHMS FOR LINEAR PROGRAMMING IN R³ AND RELATED PROBLEMS",
NIMROD MEGIDDO, SIAM J. COMPUT. Vol. 12, No. 4. November 1983.
HTH
Elmar
Kaba
> Hi.
>
> I am looking for an algorithm (or algorithms) for a certain problem
> involving line segments. I hope this is the right group for posting
> this kind of request. If not, could someone suggest a better group?
>
> I have a set of n line segments in the xy-plane. I know the endpoints
> of each line segment. In fact, for each line segment, the x-
> coordinates of the endpoints are the same. As such, line segment i can
> be specified by end-points (x1, y1(i)) and (x2, y2(i)). I assume x2 >
> x1. (Hence, none of the line segments are vertical, but some may be
> horizontal.) Let the line describing segment i be given by y(i) = a(i)
> x + b(i). For a given value of x, say x0, where x1 < x0 < x2, I want
> to know the indices of the k lines having the largest y values from
> these n line segments. Say, for example n = 6, k = 3 and for some
> value of x0 the following holds:
Hi,
Theoretically, you should get asymptotically good performance using a
sweep-line algorithm. The idea would be to divide the x-axis into
regions in which the ordering of the line segments do not change (i.e.
no intersections). For each such region you would then have the line
segments ordered by their y values (on that unambiguous region).
Practically, you'll get into numerical trouble when more than two lines
intersect in the same point, or when line segments are parallel. You
would then require either exact arithmetic or some adaptive solution
which only uses exact arithmetic when required. I wouldn't rush into
implementing this before consider other algorithms that are robust with
floating point alone.
There is some interesting additional structure in your problem. I
suspect one could find some simplification opportunities from that. For
example, let the left y-coordinates be given as
{a_1, a_2, ..., a_n} and the right ones as {b_1, b_2, ..., b_n}. Then
line segments i and j intersect
<=>
(a_i < a_j && b_i > b_j) || (a_i > a_j && b_i < b_j)
Could one find an efficient algorithm to cull the set of line segments
in advance using this condition? Not every segments affects the outcome.
After this possible pre-culling, one could compute all pairwise
intersection points (again using the condition in some clever way) to
find out the regions of non-ambiguous order.
I haven't given it full thought, but I think there's some efficient and
robust way hidden:)