CMSC 725 HOMEWORK ASSIGNMENT NUMBER 1

Date Due:  October 17, 2002

In class we mentioned the use of a PR quadtree to represent a
polygonal map which is a subdivision of space such as that formed by a
map.  We mentioned that the topology of the map was represented by a
wing-edge data structure while we also impose a PR quadtree on
vertices of the map.  In other words, we decompose the underlying
space so that each quadtree block contains at most one vertex of the
polygonal map.

Now, suppose that we want to execute a point in polygon algorithm.
In other words, given a point q, we want to find the polygon that
contains it.  One way to do this is to find the nearest vertex p,
using the PR quadtree, to q.  As there can be several edges incident
at p, we find the sector formed by the edges incident at p that
contains q.  At this point, we use the winged edge data structure to
walk around the face f containing this sector and determine if it
contains q.  If yes, then we are done.  If not, then we get the next
nearest neighbor to q and repeat the process.

1.  Show that this process will terminate.

2.  What are the worst cases in terms of how many times we will have
to invoke the nearest neighbor algorithm?  In other words, suppose
that the polygonal subdivision has n vertices, Can you describe the
spatial configurations that will lead to many vertices being examined?
How bad does the situation get?

3.  Suppose that the underlying polygonal subdivision is a
triangulation.  Repeat question 2 in this case and indicate how bad
the situation can get in terms of the number of vertices that need to
be examined.  The idea is to come up with examples of the bad cases
and try to generalize them.