B-Tree Revision

Question

Hi,

If we are looking for line intersections (horizontal and vertical lines only) and we have n lines with half of them vertical and no intersections then

Sorting the list of line end points on y value will take N log N using mergesort

Each insert delete and search of our data structue (assuming its a b-tree) will be < log n

so the total search time will be N log N

What am i missing here, if the time to sort using mergesort takes a time of N log N and insert and delete takes a time of < log n are we dropping the constant factor to give an overal time of N log N. If not then how comes < log n goes missing in total ONotation run time?

Thanks

Answer 1

The big-O notation describes the asymptotic behavior of the algorithm. That is, it describes the behavior of the algorithm as N trends towards infinity. The portion of the algorithm that takes N log N time will dwarf the portion of the algorithm that takes log N time. The significance of the log N portion diminishes to relatively nothing as N becomes large.

Answer 2

I suspect that your tutor is referring to the problem of Line Segment Intersection, which is more complex than simply sorting the segments. You'll note that this article references the Shamos–Hoey algorithm, which uses a binary tree to store the line segments and efficiently detect intersections.

Michael is correct in that using a binary tree is pointless for a one-off sort of the line segments. However, in the context of detecting intersections, sorting followed by a search will yield quadratic performance and is not the best approach, hence why line detection algorithms use binary trees.

For example, suppose you sort your line segments along the x-axis from left to right. A naive detection algorithm would then be something like:

for (int i=0; i<segs.length - 1; ++i) {
  boolean searching = true;

  for (int j=i+1; j<segs.length && searching; ++j) {
     if (segments overlap on x-axis) {
       // Check for intersection.
     } else {
       // No overlap so terminate inner loop early.
       // This is the advantage of having a sorted list.
       searching = false;
     }
  }
}

Due to the doubly-nested loop the worst case is O(n^2) and occurs when all line segments overlap on the x-axis. The best case is linear and occurs when none of the segments overlap on the x-axis.

You might want to start by implementing the naive algorithm followed by one that uses a B-tree structure.