COMP317 — Design and analysis of algorithms

Line segment intersection (Manhattan topology)

In a manhattan topology, line segments run either horizontally or vertically. Each segment is defined by a pair of end-points, each specified by a pair of coordinates in the x and y dimension.

Brute force search

Intersection of line segments can be done via a brute force method by considering each unique pair of lines and determining if they intersect. This approach is, of course, in O(n2).

Horizontal sweep

A more efficient scheme is to sweep upwards through the lines to detect intersection between lines as they are subject to scanning.
  1. Sort all end-points by inserting one at a time into a y-tree (i.e. a binary search tree ordered on the y-coordinate of each point).
  2. Through an in-order traversal of the y-tree ...
    1. remove the next point, p, from the y-tree
    2. if p is the lower end-point of a vertical line, insert it into the x-tree (i.e. a binary search tree ordered on the x-coordinate of each point)
    3. else if p is the upper point of a vertical line, remove the lower point from the x-tree
    4. else if p is the end-point of a horizontal line, remove its other end-point from the y-tree, then do a range search of the x-tree and output any vertical lines whose x-coordinate falls within the range given by the two x-coordinates of the horizontal line.
The horizontal sweep algorithm is in O(n log n).

Adding end-points to the y-tree (Step 1) is loglinear. Removing them (Step 2.1) is linear. Adding and removing vertical segment end-points to the x-tree (Step 2.2 and 2.3) is loglinear. Range searching(Step 2.4) is logarithmic. Note that each point removed from the y-tree is either added to the x-tree or it causes a range search, but not both.