When viewed graphically, each node in a 2-d tree partitions the plane into regions. For in...

When viewed graphically, each node in a 2-d tree partitions the plane into regions. For instance, Figure 1 shows the first five insertions into the 2-d tree in Figure 2. The first insertion, of p1, splits the plane into a left part and a right part. The second insertion, of p2, splits the left part into a top part and a bottom part, and so on.

a. For a given set of N items, does the order of insertion affect the final partition?

---

b. If two different insertion sequences result in the same tree, is the same partition produced?

---

c. Give a formula for the number of regions that result from the partition after N insertions.

---

d. Show the final partition for the 2-d tree in Figure 2.

Figure 1: The plane partitioned by a 2-d tree after the insertion of p1 = (53, 14), p2 = (27, 28), p3 = (30, 11), p4 = (67, 51), p5 = (70, 3)

Figure 2: Sample 2-d tree