1 Apr 1996

Outline

• Homework comments
• Dictionary ADT
• Application: line intersections

Homework comments

Game trees: make sure everyone understands the following. Say you have a finite game (guaranteed to end in some number of steps) that ends with a winner or a tie. Then either the first player has a winning strategy, or the first player has a strategy that forces at least a tie, or else the 2nd player has a winning strategy.

You may notice that sometimes the computer will make a move that leads to a pretty quick loss. This is not necessarily incorrect. If the computer realizes that all of its moves eventually lead to a loss, it may just pick one arbitrarily, which has the appearance of giving up. One interesting feature that you could add to your programs (if you wanted) is, when faced with an eventual loss, to pick the move that postpones losing as long as possible. Perhaps your opponent will make a mistake. Similarly, in case there are one or more winning moves, you might choose the one that wins quickest.

Dictionary ADT

Today we're going to discuss a "Dictionary" Abstract Data Type with the following operations:

• create_empty
• insert
• remove
• member (lookup)
• members_in_range

The first four operations are familiar. We've seen that they can be implemented in constant time (more or less) using hash table. They can also be implemented in O(log N) time using balanced search trees, where N is the number of elements in the tree when the operation is performed. You will learn how that is done in succeeding lectures. For now we'll just assume that it is true.

The members_in_range operation is new. It returns all of the values in the tree that lie between low_value and high_value. This is an example of an operation that is difficult to implement using hash functions. Why ought a tree be better for this?

Application: 2-D line intersection

We'll begin with an application: finding all of the intersections between the lines in a set of horizontal and vertical lines.

The input is a set of horizontal and vertical lines, specified by their endpoints. Consider a picture like the one below.

   |      |
---+------+----
   |      |     |
  -+------+-----+---
   |      |     |
   |            |
 --+------------+---
   |            |

Here's the algorithm that uses the members_in_range operation to do it:

1. Sort the left and right endpoints of the horizontal lines together with the x-coordinates of the vertical lines. Be sure to mark which are left endpoints, which are right endpoints, and which come from vertical lines.
2. Scan the sorted list from left to right. (Thing of this as sweeping a really long vertical line from left to right.)
   • Whenever a left endpoint is encountered, insert the y-coordinate of that line into the balanced search tree.
   • Whenever a right endpoint is encountered, remove the y-coordinate of that line from the balanced search tree.
   • Whenever a vertical line is encountered, perform a members_in_range operation using the lower endpoint as low_value and the upper endpoint as high_value. The output will be the y-cooridinates of the horizontal lines that intersect this vertical line.

As we scan from left to right, the tree contains the y-coordinates of all of the horizontal lines that intersect our sweep line.

How much time does this take?

Let N be the total number of lines. Step 1 will take O(N log N) time. Step 2 is more difficult to analyze. There are at most N insertions and N deletions, so the time spent on these operations is O(N log N). But we don't know how fast members_in_range is yet.

Implementation of the members_in_range function

The inputs will be

• root of a binary search tree
• an integer low_value
• an integer high_value
• the current x coordinate (just for printing out).

You could make this a Tree member function if you wanted. The code would look something like this:

void
members_in_range(node *root, int low, int high, int xcoord) {
    if(root == NULL) return;
    if(root->value >= low)
        members_in_range(root->left, low, high, xcoord);
    if((root->value >= low) && (root->value <= high))
        printout(root->value, xcoord);
    if(root->value <= high)
        members_in_range(root->right, low, high, xcoord);
}

It performs an inorder traversal of the tree, but doesn't explore branches where the values do not lie between low and high.

Try an example. How long does it take?

It will take O(log N + k), where k is the number of elements printed out. Why?

The search visits three types of nodes:

1. nodes on the path to the first leaf visited (these nodes are not necessarily all inserted)
2. nodes on the path to the last leaf visited
3. all other nodes visited (these are all inserted)

Well, the time is O(k + Nlog N), where k is the total number of intersections This is pretty good!