Assignment 2
Must be handed in no later than midnight on
Sunday April 2
nd
.
Question 1: [10 points] You are given a Voronoi diagram without the
pointset defining it. Show that the reconstruction of the pointset defining
the Voronoi diagram is not unique. Give conditions for a Voronoidiagram to
have a unique pointset (defining it).
Graduate students: establish some necessary and sufficient conditions for
uniqueness of the pointset and prove this.
Question 2: [15 points] For the example given in class to illustrate Kirkpatrick’s planar point location algorithm, ”run” Kirkpatrick’s algorithm, i.e.,
provide a sequence of triangulations S1, S2, ..., Sh(n)
, the directed DAG, and
a sample run through a pont location query.
Question 3: [30 points] You are asked to make a proposal for OC Transpo
to create a information system based on a GIS.
• How would you go about this? Give a plan including the key steps.
Estimate timelines and argue. (So,why may some steps take longer
than others?)
• What functionality would you build in? Give a mock-up to show how
it might look like. Obviously, no implementation is required, just give
graphical illustrations.
• Which hardware/software technologies would you use? On the client
side, what hardware and software would you allow for access to your
system. On the server side, what do you expect might be required in
terms of hardware and software.
• What GIS algorithms would you need to provide the functionality?
List for each of the functionality elements you identified above which
1
GIS algorithms (if any) would need to be available to provide this
functionality.
• Where would you get the data from? Which systems would you consult
prior to making your choice?
• How could the system evolve with time? Are there any features that
are essential and features that are nice to have? Provide the description
of a modest version of the system and a plan to increase functionality
over time, esp. in the context of digital cities.
Question 4: [25 points] All travel for this questions is on the (2-d) Euclidean
plane. A train has been shot at during a travel between cities A and B. The
train has left city A at noon and arrived at city B at 18:00. The train was
traveling at a constant speed (no acceleration, no breaking).. A suspect is
under investigation for having shot at the train. The RCMP has tracked
the suspect’s cell phone during that day and has available three locations
and the times the suspect was at these locations. Assume that the suspect
travels also at a cosntant speed. Using the framework for spatio-temporal
GIS described in class (March 15th
, ..), show graphically how we can help the
RCMP. Be precise in your illustrations.
Graduate students: The train had three intermediate stops (between
A and B). The shot occured from inside the train. The suspect was not one
of the passengers boarding at A or leaving the train at B (CCTV survelliance
footage). How could we know if the suspect got on and off the train at any
of three intermediate locations?