Homework 1 (due 4/7)
CSC 543

We covered material from Chapter 1 of the textbook and from the first chapter of Shekhar, Chawla's Spatial Databases, a Tour.

One correction: bitmap indices can be good for indexing fields with small number of values (actually they were created for that).

Submission: you can submit the homework by hardcopy in class or by sending it to me as an email. (For part 1, include a URL.)

1. [Jogging App, 40pt] Using the google maps API create a web-page (as we did in class) that allows you to click on a sequence of points on the map, draws a polygonal line connecting the points (in the order they were clicked) and maintains the current length of the polygonal line (the sum of the separate line segments). Hint: You need to sign up for a key for the Google Maps API and you need to be able to upload your page to a web-server. We saw several examples in class that illustrate most of the ingredients you need for this problem (including distance between two points). The one new ingredient you need to research is how to add line segments between consecutive points (or markers).

2. [How not to do it] Suppose you have a table city with (for simplicity) x,y coordinates. E.g.:

a) (15pt) Write an SQL query that returns all pairs of cities that are within a distance of 500 miles of each other.

b) [Extra Credit, 20pt] Write an SQL query that determines all pairs of flight paths between cities that intersect (e.g. San Francisco to New York crosses Los Angeles to Chicago). Make the simplifying assumption that flight paths are straight line segments. 

3. [Poylgons, 15pt] A polygon is a region in the plane bounded by a sequence of consecutive line segments (see textbook, pages 32/33). Consider the following properties of polygons:

  1.  simple (no two line segments cross)
  2. convex (any two points in the polygon can be connected by a straight line lying within the polygon)
  3. area

For each property briefly discuss whether it can be expressed in traditional relational SQL (without spatial extensions) and whether doing so would be efficient or not (compared to an SDBMS implementation). 


Marcus Schaefer
Last updated: April 1st, 2009.