2

I am trying to solve this question, but I am stuck on how to make this work. I will post the question, and then explain where I am in it.

Given a set of horizontal line segments and vertical lines of total size n, we want to compute the number of horizontal segments intersected by each vertical line. The algorithm should be of complexity O(n*logn), and should be achieved by sorting, following by a linear scan. A horizontal segment is specified by two x-coordinates and a y-coordinate, while a vertical line is specified by a single x-coordinate. Output is an array of numbers count[l], one for each vertical line l.

For the sorting, I would think I would sort the entire set by which line finishes earliest (i.e. smallest second x-coordinate, or in the case of a vertical line, just its one x-coordinate) so that I have a linear progression through all of the lines. I am just confused as to how the linear scan following the sorting should be played out. If anyone has any hints, tips, or guidelines, I would appreciate it!

PS: This is practise for a midterm, so while it's not necessarily homework, I will still mark it as such.

corsiKa
  • 81,495
  • 25
  • 153
  • 204
Tesla
  • 822
  • 2
  • 13
  • 27

2 Answers2

0

The question can be written otherwise:

Foreach horizontal segment (x1,x2), find all the vertical lines that intersect it. You can do that by sorting the vertical lines getting a set of position x.

Now, run a binary search and position x1 in the set of x's, let's call its position p1. Do the same for x2, p2. The number of intersection for the given segment equals p2-p1.

Do that for all the horizontal segements.

Sorting the vertical segments will take O(klog(k)). Every search is done in O(log(k)) and is done twice for each segment: O(mlog(k)). Where k is the number of vertical lines and m the number of horizontal segments. n = m+k > m,k therefor, the overall complexity is O(nlogn).

Samy Arous
  • 6,794
  • 13
  • 20
  • Hmm, I am a little confused. For example if you have one horizontal line (2,6) and a vertical line (5), doing the binary search for both 2 and 6, you would get a set (2,5,6) with p1 = 0, and p2 = 2, correct? Then using p2-p1+1 you would get 3, as opposed to the answer which is just 1. Am I misinterpreting something? – Tesla Jun 04 '12 at 20:05
  • Nop, I've made a mistake there. Didn't think it through. The correct value shouldn't be hard to find though. The result is p1 = 0, p2 = 1 and not 2. You need to treat 2 cases, one when, the binary_search find the value and one when the binary_search return an empty slot. I'm too sleepy to solve this, but shouldn't be hard to guess :) – Samy Arous Jun 04 '12 at 20:16
  • Also, I believe it is a bit difficult to come up with the number of horizontal lines each vertical line crosses with this method, which is the desired output. – Tesla Jun 04 '12 at 20:58
  • Of course it does :) if a segment intersect a line then the line intersect the segment. It's a bijection. Every time a segment intersect a line, just increment the corresponding counter. At the end of the algorithm you will have your count array. As I said I'm kinda of tired right now. I'll implement this tomorrow and push it here. – Samy Arous Jun 04 '12 at 21:21
  • Well how I envisioned your solution was that after the sorting, I would have 1 loop that iterates through all of the horizontal line segments, and each iteration does 2 binary searches and comes up with the number of vertical lines that cross the current horizontal line segment. I didn't see a simple way of identifying which vertical lines did the intersecting. I think you could add a another loop that increments the counter array for all n "p1 < n < p2", but does this change complexity. Anyways, thanks for the help either way. I look forward to your answer tomorrow. – Tesla Jun 04 '12 at 21:32
0

First you put all the start/end points of the horizontal segments. and the x-coordinates of the vertical lines, together.

Second, sort them. Let's call the sorted list L.

Third, imaging there is a vertical scanning line, starting from the left most of your points list L, moving to the right.

Whenever the scanning line hits a point, it's either a start point of a horizontal segment, or an end point of a horizontal segment, or a vertical line.

And you can do two things when you move the scanning line:

1) keep the set of horizontal segments that the scanning line currently intersects (whenever it's a start/end point of a horizontal segment, add/delete it to/from the set)

2) whenever it's a vertical line, you know that vertical line is intersected by all the horizontal segments in the set you are maintaining by the way in 1)

So, sorting is O(nlogn); moving the scanning line through the sorted list L is O(n)

All in all, it's O(nlogn)

xvatar
  • 3,229
  • 17
  • 20
  • I am a little confused as how to this would be implemented in an algorithm, while maintaining the complexity requirement. Each point is just a set (x1,x2) for horizontal line segments and (x) for vertical lines. If you were to break up all the points and put them into one list, how do you know which one is a start/end/vertical line? – Tesla Jun 05 '12 at 19:26
  • @Tesla an intuitive way would be creating a structure, say `Point`, that has two fields, one field is the coordinate, the other one indicates whether it's a start point, end point, or a vertical line. So you can sort the list of `Point` based on the first field, and check what it is based on the second field. – xvatar Jun 05 '12 at 20:24