There are 10 different non-empty intervals that have the numbers 1, 2, 3, 4, or 5 as their endpoints.
Draw an interval tree for range reporting with these intervals, based on a binary tree whose root node stores the number 3 and whose two children store the numbers 1 and 4. For each node of the interval tree write the two sorted orders of intervals stored at that node. (If some intervals are tied in this sorted order you may break the ties arbitrarily.)
Draw a segment tree for range counting with the same 10 intervals, based on a binary tree whose root node stores the number 3 and whose two children store the numbers 1 and 4.
Find a formula for the number of nodes in a segment tree, as a function of the number of distinct endpoints in a given system of intervals. (For instance, for problem 1, your formula should give the number of nodes for five endpoints.) Explain why there cannot be an exact formula like this for interval trees.
If you have a system of axis-parallel squares in the plane, with no two squares having boundaries on the same axis-parallel line, are they pseudo-disks? Explain why or why not.
Draw two squares whose sides are not parallel to each other that do not form pseudo-disks with respect to each other.
Suppose we have a robot in the shape of a circle, moving in two dimensions (like a Roomba) with radius 1 and center at (0,0). Draw a system of line segments that enclose the robot without touching it or each other, preventing the robot from moving arbitrarily far from the robot. Also draw the expanded obstacles for your segments.