Homework for CMSC 828M due on Tuesday, April 8, 2008.

1.  Explain the relationship between convexity and a monotone subdivision
    (either x or y).

2.  How would you implement (adapt) a region quadtree (regular 
    decomposition) to the representation of data on a sphere when we 
    project the cube onto the surface of the sphere.  In this case, each 
    face is a spherical square.  What you need to explain is how you will 
    decompose the space.

3.  What is the advantage of projecting the Platonic solid (e.g.,
    cube) onto the sphere over projecting the sphere onto the cube?
    In other words, suppose that you are representing spherical point
    data using a hierarchical representation such as the spherical
    variant of the PR quadtree, how is the execution of queries such
    as point location and/or nearest point affected by the two
    representations.  Hint:  Look at how you would implement them.