Problems Based on Textbook

Odd number problems may be used in the classroom discussions. Even number problems will be used in home-works.

Chapter 2: Understanding an Conceptual Models

Consider questions A through F:
1. A. What is the maximum number of directed arcs associated with an area?
2. B. What is the minimum number of directed arcs associated with an area?
3. C. What is the maximum number of left-bounding area for a given arc?
4. D. What is the minimum number of left-bounding area for a given arc?
5. E. What is the maximum number of nodes for a given area?
6. F. What is the minimum number of nodes for a given area?
Q 2.1 : Answer questions A-F for Fig 2.15 (pp. 65) for the planar configuration of nodes, directed arcs and areas. Each answer is a non-negative whole number.
Q 2.2 : Answer questions A-F in context of the EER diagram in Fig 2.16 (pp. 65), where answers are restricted to 0, 1 or many. Are there any surprises (e.g. ambiguities, violation of your knowledge of geometry)? Explain the surprises in terms of the purpose of conceptual data model such as EER. Suggest ways to improve EER diagram to address the surprises. Limit your narrative to 100 words.
Q 2.3 : Which of following geometric concepts are modeled by planar configurations described via EER diagram in Fig. 2.16 (pp. 65): triangle, circle, hexagon, ellipse, cube, parabola, spiral. Briefly explain.
Q 2.4 : Draw an EER diagram for the spaghetti data model using the narrative and examples in sec. 5.3.1 (pp. 177-178).
Q 2.5 : Convert non-normal table ARC instance in Table 5.3 (pp. 180) for the node-arc-area model (sec. 5.3.2, pp. 179-181) into instances for normalized tables (e.g. ARC, POLYGON, POLYLINE, POINT, NODE). Augment rows in normalized table instances POINT, and POLYLINE using more detailed planar configuration in Figure 5.7 (pp. 178). For simplicity, do not fill in X_COORD and Y_COORD in POINT table. Compare augmented normalized tables the EER diagram of Fig. 5.9 (pp. 181). List EER cardinality constraints violated by normalized table instances. Discuss if these cardinality constraints should be revised.
Q 2.6 : Review the queries in Laboratory 1 and Laboratory 2. Classify those by relational algebra operations of select, project, and join.
Q 2.6 : Review spatial analysis with GIS subsection of the wikipedia article on Geographic information system Classify following GIS operation by relational algebra operations of select, project, and join:
1. Slope and aspect, e.g. determine high slope area given elevation data. Flag soil erosion risk for locations close to rivers, with high slopes, poor vegetation and soil.
2. Topological modeling, e.g. list countries adjacent Russia.
3. Map overlay of soil-type polygons, and high-slope polygons, to identify erosion risks.
4. Networks (e.g. If a pollutant is spilled in a river, how long would it take the pollutant to reach a drinking water plant downstream?)
5. Network, Slope e.g. determine drainage basin for each river given elevation and river data.
Note that some GIS operations can not be represented in relational algebra. This is explored in the next question.
Q 2.7 : Relational algebra (with operations of select, project, join) query language (e.e. SQL 1986) is not as expressive as general programming languages such as Java, Python, Perl, C++, etc. It can not represent transitive closure queries such as shortest path given edge and node tables. Revisit the pottery example in Chapter 1 of the textbook. List those queries in pottery example, which can not be represented in relational algebra languages (e.g. SQL 1986). Also find out if new generation of SQL support transitive closure.

Chapter 3: Fundamental Spatial Concepts

Q 3.1 : Which branch (e.g. set theory, topology, metric space, Euclidean space, Graph Theory, Fractal Geometry) of mathematics is used to formalize relational databases discussed in chapter 2.2 ?
Q 3.2 : Which branch (e.g. set theory, topology, metric space, Euclidean space, Graph Theory, Fractal Geometry) of mathematics is used to formalize following spatial concepts: Universal Transverse Mercator (UTM), geodesic distance, direction (e.g. North, East), shortest path (for driving on urban roads), boundary, space-filling curves (Fig. 6.8, pp. 234), planar configurations such as polygons, straight-line distance, convex polygon, landslide probability (chapter 9.4, pp. 350) interior, symmetric relationship, complement, exterior.
Q 3.3 : Consider transformation classes such as Euclidean (e.g. translation), Similarity (e.g. rotation), Affine (e.g. rotation, reflection), Projective (e.g. slide projectors), and Topological (elastic deformation without tear, e.g. balloon expansion). Which of the following spatial properties are preserved by each? shape, size, distance, direction (e.g. above, below), occlusion (e.g. in front of), parallel lines, overlap, inside.
Q 3.4 : Review wikipedia article on map projections and article on upsidedown maps. Classify following map projections in to the most specific transform classes listed in previous question: cylindrical, Azimuthal (projection onto a plane), upside down (South up).
Q 3.5 : Review the definitions of trees, directed acyclic graphs, planar graphs and general graphs (non-planar allowing cycles) in section 3.4 (pp. 117-122). Which kind of graph will you use to model the following spatial phenomena: road networks, and river networks. Briefly justify your choices.
Q 3.6 : Recall definition of neighborhood in point set topology. Which of the following collection of sets satisfy these properties, each member set is a collection of points within fixed value of a function, defined in one of the following ways:
- Euclidean (straight-line) distance on a place
- Geodesic or great-circle distance on a sphere.
- Walking time between points in a hilly terrain.
- Total travel-time via public transportation and walking (e.g. Fig. 3.51, pp. 127).
Briefly justify your answers.
Q 3.7 : Recall non-negative, symmetry, and triangle inequality properties of the distance function in metric spaces. Which of the following functions satisfy these properties?
- Euclidean (straight-line) distance between points on a plane.
- Manhattan distance between points on a planar grid.
- Geodesic or great-circle distance on a sphere.
- Walking time between points in a hilly terrain.
- Typical flying time between cities.
Briefly justify your answers.
Q 3.8 : Euclidean and metric spaces are often emphasized in study of geometry and vector algebra. Why is Metric space inadequate for understanding GIS? Provide specific examples and formal arguments showing inadequacy of Metric space to model travel-time on network spaces. (Hint: use distance function properties of symmetry, triangle inequality, etc.)
Q 3.9 : Review definition of planar graph from wikipedia article. Revise Fig. 3.44(b) to make it K3,3 and thus non-planar. Is usual graph representation of urban roadmaps (e.g New York city) planar? Assume that nodes represent road-intersections and edges represent road-segments connecting adjacent intersections. Recall that urban areas may have tunnels and fly-overs.
Q 3.10 : Which of the following will benefit from modeling as fractals rather than line-strings?
1. Specific space-filling curves in Figure 6.8 (pp. 234).
2. Coast-line, road center-lines, streams in a river delta, snow-flakes

Chapter 4: Models of Geospatial Information

Q 4.1a : Review map layers in National Atlas. For each layer in Climate and Map Reference chapters into field based and object based models. Briefly justify your answer using definitions of field based and object based models.
Q 4.1b : Review a presentation on map algebra . Classify following operations on slide 12 into local, focal and zonal operations on an elevation field defined over a grid (square based regular planar tessellation):
1. ASPECT: identifies the direction of maximum rate of change in z value from each cell.
2. BOUNDARYCLEAN: smoothes the boundary between zones by expanding and shrinking the boundary.
3. HILLSHADE: creates a shaded relief grid from a grid by considering the sun illumination angle and shadows.
4. INT: converts input floating-point values to integer values through truncation.
5. ISNULL: returns .1. if the input value is NODATA, and .0. if it is not.
6. MEAN: uses multiple input grids to determine the mean value on a cell-by-cell basis.
7. SLOPE: identifies the rate of maximum change in z value from each cell.
8. ZONALAREA: calculates the area of each zone in the input grid.
Q 4.1c : Review an article on user interfaces of map algebra . Assume that a 1 meter by 1 meter grid over a regular square planar tessellation. Many fields are defined over this grid to represent elevation, slope, streams, soil-type, vegetation etc. These fields are used to derive soil-erosion vulnerability for each cell. A cell is vulnerable to soil-erosion if it is within 50 meters of a stream, has a steep slope, little vegetation and poor soil-type. Figure 6 shows a composition of these field operations. Classify operation in Figure 6 (pp. 50) into local, focal and zonal operations:
1. Buffer (cell within 50m of a stream)
2. Testing slope is steep
3. Sum of local properties
4. Product (or conjunction of local properties)
Q 4.1d (Source) : Game of life is a binary-valued field defined over a rectangular grid of cells. A cell have have a value of "occupied" (represented by number 1) or "unoccupied" (represented by number 0) in a given generation. A simple neighborhood is defined using eight cells sharing a corner or an edge, i.e. adjacent horizontally, vertically or diagonally. A new generation is defined using following rules:
1. A occupied cell with two occupied neighbors remains occupied.
2. An unoccupied cell with two or three occupied neighbors becomes occupied.
3. All other cells become unoccupied.
Define a map algebra expression to define new generation from last generation. Assume that the following map algebra operations are available:
1. Add(field F, Field G): Increase each element f F by corresponding element of G
2. Subtract(field F, Field G): Reduce each element f F by corresponding element of G
3. Multiply(field F, integer J): multiply each element of F by integer J
4. Focal_Sum(field F, Neighborhood_size N): for each element of F, computes sum of values in the square neighborhood of size N by N cells. One may use N = 3 to define the neighborhood with 8 adjacent cells.
5. Threshold(field F, integer J): Replace each element of F by 1 if the element if larger than J. Otherwise the element is replaced by 0.
Q 4.2 : Consider a spatial framework defined by latitudes and longitude (1 degree by 1 degree cells) to represent (time-average) annual temperatures for years 1900 to present over the surface of Earth. Consider zones defined by countries and assume that each cell belongs to a unique zone. For simplicity, ignore cell convergence in polar regions. Classify following operations into local, focal, zonal operations:
1. Determine warmest temperature (or year) for each cell.
2. Determine warmest cell in each country in year 2000.
3. Identify country with highest average cell temperature in year 2000.
4. For each cell, compute spatial-neighborhood average temperature in the year 2000.
5. For each cell, compute heat-island-factor as the difference between its temperature and its spatial-neighborhood average temperature for the year 2000. Assume the results of previous step were available as an input for this step.
6. For each country, list the cell with highest value of heat-island-factor. Assume the results of previous step were available as an input for this step.
7. Compute average annual temperature of surface of Earth for each year.
Q 4.3 : Recall the Network space and graph models discussed in chapter 3.4 (pp. 117-...). Compare field-based and object-based models for network datasets such as road-maps, rivers, etc. for modeling flow of vehicles, water, etc.
Q 4.4 : Consider a Euclidean spatial datasets with three layers: (i) countries represented as polygons. (ii) continents represented as polygons. (iii) Lakes represented as polygons. Consult a world map (e.g. Google Maps to classify following pairs of spatial objects into one of 8 topological relationships between cells in the Euclidean place listed in Table 4.3 (pp. 162):
1. Austria, Europe
2. USA, Canada
3. Europe, Asia
4. Lake Superior, USA
5. Turkey, Europe
6. Lesotho, South Africa
Q 4.5a : Review the queries in Laboratory 2. Classify those by following criteria:
1. Spatial data model: field-based, object-based.
2. Spatial Operation: Euclidean, Topological, Set-theory.
Q 4.5b : Assume the availability of following spatial tables: cities(name, city_center_point), country(name, boundary_polygon), river(name, linestring), and Hurricane_trajectories(name, time-point, boundary_polygon), Identify the spatial operation from Table 4.2 (pp. 158) in the textbook used to model following english queries in spatial SQL:
1. List names of all Canadian cities.
2. List neighbors of China.
3. Which country has the highest number of neighbors?
4. List countrys river Nile flows through.
5. List cities within 50 miles of river Nile.
6. Calculate area of a buffer of 10 miles around rile Nile.
7. List hurricanes making land-fall into USA at a given time.
8. Q 4.6 : Summarize the 9-intersection model of binary topological relationships (section 4.4.2, pp. 162) using nine boolean (empty/non-empty) tests. Discuss if it distinguish between 2-overlaps (Figure 4.23, pp. 160) and overlaps (Fig. 4.22, pp. 160). Explain. Limit your answer to 50 words.

Chapter 5: Representation and Algorithms

Q 5.1a : Review three typical questions in computational geometry listed in section 5.1.1 (pp. 169-172), assuming that the relevant dataset are inside main memory. For the following GIS problem, state if it can not be solved using algorithms. If affirmative, name an efficient algorithm for the problem:
1. Geo-locate all human settlements e.g. tents (or usable roads) a few days after Haiti earthquake, given an aerial image (e.g. see examples: 1 , 2 ) a few days after Jan. 2010 earthquake.
2. Given a digital satellite image, create an object based model for water bodies including wells (points), streams (linestring) and lakes (polygons).
  Note: Students interested in the state of the art on such problem, may find a recent Textbook section 5.6 titled vectorization and rasterization (pp. 207-211) interesting.
3. Given a news article (e.g. those from Google News), photograph, or video-clip, identify the geographic location it is describing.
  Note: Students interested in the state of the art on such problems, may find a recent New York Times article interesting.
4. Find the elevation of a given point of interest (POI), given a regular tessellation based representation of elevation field defined over the USA. For simplicity, use square based tesselation of a Euclidean plane. Assume the availability of a geo-coding service to convert POI to grid row and column. For simplicity, focus on non-nested tessellations.
5. Revisit the previous problem using regular triangular tesselation. List your assumptions about the geo-coding service.
6. Revisit the previous problem using irregular triangular tesselation. List your assumptions about the geo-coding service.
7. Given postal addresses of hotels, determine the hotel closest to a specified point of interest (POI), e.g. the Mall of America. Use Euclidean space and straight-line distance for simplicity. Assume the availability of a geo-coding service to convert postal addresses to geographic point-locations.
8. Revisit the previous problem using Network space and network-distances. Assume roadmaps are represented as a graph using road-intersections as nodes and road-segments connecting adjacent intersections as edges. Also available is a a geo-coding service to place hotels and POIs to nearest road-intersection (nodes).
9. Given a graph representation of a road-network (or electricity distribution network), determine if it is connected.

Q 5.1b : Worst-case asymptotic time complexity from theoretical computer science compares alternative algorithms for a given problem, assuming that the entire dataset is in (a very large and expensive) main memory, the software runs on a single user system without concurrency, and response-times are more important than throughput, power-consumption, hardware-costs, etc. Compare the strengths and weaknesses of this measure relative to one of the alternative measures listed below:

Area	Measure
DBMS : SQL Query Processing	Number of I/O operations
Transaction Processing DBMS	Transactions Per Second
Traditional Computer Architecture	Instructions Per Second
Embedded Systems, e.g. cell-phones	Power consumption, (e.g. paper )
Parallel Computing	Scalability (e.g. iso-efficiency , energy-bounded )
Distributed Computing	Number of Messages (e.g. paper )

Can different measures favor different algorithms for a given problem instance? Why? Briefly justify your answer via an example.

Q 5.1c : Review the short 2-page paper titled An O(nlogn) implementation of the Douglas-Peucker algorithm for line simplification in 1994 Symposium on Computational Geometry. It describes a straight-forward implementation with worst-case running time of O(N*N) and a second implementation using path-hull data-structure with O(N* log(N)) running time. However the authors conclude that Unfortunately for us, the statistical properties of cartographic data usually means that the straightforward implementation is slightly faster than the path hull implementation. Explain in 50 words or less.
Note: Additional details are provided in a full length paper ( pdf ). path hull implementation. Since).
Q 5.1d : Worst-case asymptotic time complexity from theoretical computer science suggests "that algorithms that are of order O(k raised to n) (i.e. exponential time complexity) are interactable, because they can only be used for very small input sizes" (first paragraph, pp. 172). However, data mining software for association rule learning often uses such algorithms (e.g. apriori) for mining very large market basket datasets with millions of item-types and billions of transactions. Explain this apparent paradox. Limit your answer to 100 words.
Q 5.2 : Consider the rough guide to worst-case time complexity of algorithms (Table 5.2, pp. 171). Classify the complexity of following algorithms into classes of constant, logarithmic, linear, n*log(n), polynomial and exponential: Assume relevant line-strings have N segments, polygons have N vertices and graphs have N vertices and E edges.
1. Douglas-Pucker algorithm to discretize arcs (sec. 5.2.3, pp. 176-177)
2. Compute area of a simple polygon (sec. 5.5.1, pp. 195-197)
3. Compute centroid of a polygon (sec. 5.5.1, pp. 195-197)
4. Point in polygon (sec. 5.5.2, pp. 197-199)
5. Intersection or a polygon-pair, each with N vertices (sec. 5.5.3, pp. 201-202)
6. Depth-first or breadth-first graph traversal (sec. 5.7.2, pp. 213-217)
7. Single-pair shortest path in a graph (sec. 5.7.2, pp. 213-217)
8. All-pair shortest paths in a graph (sec. 5.7.2, pp. 213-217)
9. Hamiltonian circuit (or Traveling salesman problem) (sec. 5.7.2, pp. 213-217)
Q 5.3a : Field-based and object-based models of geospatial information are relevant to paper maps as well as digital maps. However, paper is a continuous media, where as computers represent discrete media due finite representation of numbers. What are the implication of discrete nature of computers for object-based models of geospatial information? Justify your answer via illustrative examples. Limit the answer to 200 words.
Q 5.3b : A popular GIS textbook suggests that " Positions measured from paper maps should be accurate to about 0.5mm on the map. Multiplying this by the scale of the map gives corresponding distance on the ground. " This corresponds to a ground distance range of 62.5cm to 5 km for map scales range from 1:1,250 to 1:10,000,000. Characterize the effect of discrete digital representation of number (e.g. those representing latitude, longitude, and elevation of a geo-location) on geo-accuracy. For simplicity, assume that we use fixed point numbers with 3 digits before decimal to represent latitudes, longitude, and elevation, even though their values range in [90N..90S] degrees and [-180..180] degrees respectively. Also assume that a fixed-point number may have 5 digits in 16-bit computers, 9 digits in 32-bit computers and 18 digits in 64-bit computers. What positional accuracies (in centimeter) are implied by 5-digit, 9-digit and 18-digit numbers ? How do these compare with the accuracies of measurement instruments such as (differential) gps?
Q 5.3c : Use cases such as tax-calculation and financial audit have provided compelling reasons for limiting errors in arithmetic calculation software for tax preparation, banking, purchase order, general ledger, electronic payment, etc. Propose a couple of potential GIS use cases, which may motivate limiting errors in geometric GIS calculations related to position, elevation, length, area, speed, velocity, direction of travel, slope, gradient, water-flow direction, flood-plain maps (e.g. 1 , 2 , 3 ) to recommend flood-insurance, etc. Storyboard scenarios to show potential adverse affects of not limiting geometric accuracy in context of such applications. How do people deal with lack of error-bounds in present-day GIS technologies while making policies and decisions (e.g. those related to requiring flood-insurance)? What changes may occur in such policies and decisions if future GIS technologies could bound errors?
(Hint: Clock synchronization algorithms for computer networks were funded by military due to potential impact on determination of travel-direction for a adversarial missile, based on detection-time at two sensors at different locations.)
Q 5.3d : Some believe that land-surveying (and thus geometry and GIS) were initiated by the societal need to keep track of land-ownership as humans moved from a nomadic life-style to agriculture. Geo-data error in this context has led to may conflicts including an ongoing Tennesse-Georgia state boundary dispute (see 1 , 2 , 3 , 4 , and 5 ) due to recent draught. What geo-technology was the source of this error in geographic data? What risks do you envisage in use of GIS software which do not bound errors in geometric computations?
Q 5.3e : Consider use of the Douglas-Pucker algorithm to approximate an arc by a linestring. What can you say about the number of points in the linestring if the arc were a
1. semi-circle, where error bound limits can not reached without using at least 5 equal-size line-segments.
2. a line-string, e.g. one shown in Fig. 6.8 (pp. 234)
3. a fractal, e.g. upper half of a snow-flake (Fig. 3.53, pp. 130)
Q 5.3f : Which of the following properties are true for the Douglas-Pucker Algorithm (DPA) for discretizing simple arcs? Briefly justify your answer.
1. Correctness: Linestring produced by DPA will meet the specified error threshold. In addition, DPA terminates of all given arc.
2. Solution quality: The line-string produced by DPA is optimal in number of vertices. In other words, any line-string (discretizing given arc withing the error threshold) will have at least as many points as the line-string produced by DPA.
3. Response time: If input arc is a linestring with N point, worst-case computational complexity of DPA is no worse than O(N*N).
4. Solution property: If input arc is symmetric along the perpendicular bi-sector of the line joining arc's end-points, the number of points in the linestring produced by DPA will be a integral power of 2.
Assume that a finite error threshold is provided for distance between linestring and farthest point on arc.
Q 5.4 : Consider alternative data models for spatial object domain (section 5.3, pp. 177-187) including spagetti, node-arc-area, DCEL, etc. Which data model is closest to the following popular formats:
1. GML Simple Features .
2. ESRI Shapefile: wikipedia article .
Briefly justify your answer assuming Euclidean space.
Q 5.5(a) : Consider the spatial objects with holes and islands (Figure 5.14, pp. 187). Discuss their possible representations in alternative data models for spatial object domain including spagetti, node-arc-area, and DCEL (section 5.3, pp. 177-187).
Q 5.5(b) : Extended node-arc-area model (Chapter 5.3.2, pp. 177-181) has three geometric entities: points, polyline, and polygons. Which additional spatial data-types are supported by standards like Simple Features and Well-known text ? Conjecture reasons for additional data-types in standards. Briefly justify your answer.
Q 5.5(c) : Match the algorithms described in section 5.5 (fundamental geometric algorithms, pp. 194-207) with the spatial operations listed in Table 4.2 (pp. 158). Which spatial operations are directly supported by the algorithms described in section 5.5? Which spatial operations are not directly supported ?
Q 5.5(d) : Section 5.5 (pp. 194-207) provides formulas for many Euclidean operations in Table 4.2 (pp. 158) including distance, angle/bearing, area and centroid. However, it did not provide formulas/algorithms for length and perimeter operations. Proposed algorithms for computing length of a simple linestring and perimeter of a simple polygon. What are worst-case and average-case time-complexities of your algorithms ?
Q 5.5(e) : Section 5.5 (pp. 194-207) provides only one topological algorithm titled point-in-polygon, which is at best a building block towards algorithms for binary topological operations (i.e. overlaps, is_inside, covers and meets) in Table 4.2 (pp. 158). Other building blocks are tests for collinearity, point-on-segment, segment intersection, etc. Assume the availability of the following statistics about relationships among corner-points and sides (i.e. line-segments defining boundaries) of simple polygons A and B:
1. S1 = Fraction of corner-points of A, which are inside B
2. S2 = Fraction of corner-points of B, which are inside A
3. S3 = Fraction of corner-points of A which are on a side of B
4. S4 = Fraction of corner-points of B which are on a side of A
5. S5 = Fraction of sides of A which intersect some side of B
6. S6 = Fraction of sides of B which intersect some side of B
Propose algorithms for all four binary topological operation: overlaps, is_inside, covers and meets. Use tests on the given statistics as appropriate. What are worst-case and average-case time-complexities of your algorithms ? How can average-case time-complexities of your algorithms be reduced using minimum orthogonal bounding rectangles for polygons A and B?
Q 5.5(f) : Section 5.5 (pp. 194-207) provides only primitives (e.g. point-in-polygon, collinearity, point-on-segment, segment intersection, etc.), but not algorithms for set-based operations (e.g. intersection, union, difference) in Table 4.2 (pp. 158). Using these primitive, design a simple algorithm to determine the intersecting area of two triangles. Test your algorithms for different topological cases including in inside, covers, overlaps and meets. (Hint: Consider algorithm proposed in a short 1-page paper titled An efficient and simple polygon intersection algorithm .)
Q 5.5(g) : Consider the following polygon intersection algorithm from stackoverflow website based on triangulation:
1. Triangulate each polygon. Compare all the triangles from P pairwise with all the triangles from Q to detect intersections. Any pair of intersecting triangles can be broken into smaller triangles each of which is in P, in Q, or in the intersection. (Whatever you used in step 1 can be reused to help with this.) Only keep triangles that are in the intersection.
2. Compute the neighbors of each triangle, by comparing them pairwise, and build an adjacency graph. This graph will contain one connected subgraph for each polygon in the intersection of P and Q.
3. For each such subgraph, pick a triangle, walk to the edge, and then walk around the edge, producing the segments bounding the corresponding output polygon.
Determine the worst-case time-complexity of this algorithm.
Q 5.6 : Consider alternative representation of field-based models (section 5.4, pp. 187-194) including tesselation (regular, irregular), triangulation, vornoi diagrams, etc. Which data model is closest to the following popular formats:
1. Raster: wikipedia article .
2. Digital Elevation Model (DEM): wikipedia article .
Briefly justify your answer assuming Euclidean space.
Q 5.7 : Revisit the geospatial data models listed in previous question for a simple geo-spatial dataset (e.g. city centers, and country boundaries). Which of the following questions can be answered accurately by various models:
1. Which citycenters are in southern hemisphere ?
2. What is the Euclidean distance between two nodes?
3. What is length of a given directed arc ?
4. Which countries are adjacent to USA ?
5. What is the minimum number of countries visited by a land-traveler going from France to Turkey ?
Briefly justify your answer.

Q 5.8 : Review the article on PostGIS in Encyclopedia of GIS (pp. 891-898). Compare the spatial object model used in this article with the one described in the the Textbook Chapter 4.4 (pp. 151-163) in following areas:

Criteria	Textbook Chapter 4.4	PostGIS Article
Spatial Object Types	Textbook Fig. 4.21 (pp. 157)	Figure 1, 2 (pp. 892-893)
Spatial Operations	Textbook Table 4.2 (pp. 158)	Paragraphs (pp. 893), Figure 3 (pp. 894)

Summarize the differences. Which differences may be related to the difference between 4-intersection model and 9-intersection model on page 162 of textbook ?

Q 5.9a : Network Representation : Compare the adjacency matrix and adjacency list representations discussed in the textbook with the following:
- Origin-destination trip tables to represent Trip distributions or zonal interchange.
- Oracle Spatial network data model with tables such as node( node_id, node_name, node_type, ..., hierarchy_level, parent_node_id), link( link_id, link_name, start_node_id, end_node_id, link_geometry, link_cost, ...), path( path_id, path_type, start_node_id, end_node_id, cost, ...), and path_Link( path_id, link_id, seq_no).
Q 5.9b : Network Algorithms: Consider shortest path computation on a simple graph representing grid-like road networks in downtown areas without geographic obtacles such as rivers, hills, parks, large multi-block building etc. Suppose there are sixteen nodes with following ids, x-coordinates, and y-coordinates: (aa, 1, 1), (ab, 1, 2), (ac, 1, 3), (ad, 1, 4), (ba, 2, 1), (bb, 2, 2), (bc, 2, 3), (bd, 2, 4), (ca, 3, 1), (cb, 3, 2), (cc, 3, 3), (cd, 3, 4), (da, 4, 1), (db, 4, 2), (dc, 4, 3), (dd, 4, 4). Two nodes are connected if their distances are less than equal to 1 unit. Compare sets of node expanded by Dijktra's algorithm and A* (with euclidean distance heuristic) if start node is aa and destination is ad. Which algorithm expands fewer nodes? Briefly explain the difference in the number of nodes expanded.
Q 5.9c : Network Representation : Discuss how the following properties of road-networks may (or may not) be represent using the adjacency matrix and adjacency list representations discussed in the textbook :
- Length of road segments connecting adjacent road intersections
- One-way road-segments
- Turn restrictions, e.g. no left turn
- Time-travel for a road-segment as a function of time-of-the-day.

Chapter 6: Structures and Access Methods

Q 6.1 : Why do spatial DBMS use different data-structures and access methods than those used in traditional relational DBMS focussed on numbers, text strings, currency, etc. ? Justify your answer with a brief example. Limit answer to 200 words and a diagram.
Q 6.2 : Compare and contrast R-trees and R+-trees. Consider a minimum orthogonal bounding rectangle for rectangle T and L. Add it to the set of rectangles in Fig. 6.29 (pp. 253) and Fig. 6.30 (pp. 254). Redraw the R-tree and R+tree in Fig. 6.29 and 6.30 if this new rectangle is inserted. Briefly justify your solutions by recalling how R-tree and R+tree deal with large objects based on narrative of section 6.6.2 (pp. 252-254)?
Q 6.3 : Classify the data structures and access methods in list A using embedding space (list B) and data types (list C):
- List A: ordered files, B-tree, Peano-Hilbert curves, R-tree, Quad-trees, R+-tree, Grid files, 2D-tree, BSP-tree, QTM Quad-tree.
- Space list B: one dimension (linear), plane (2 dimensions), sphere surface
- Data type list C: objects (e.g. points, rectangles), fields (e.g. rastor)
Q 6.4 : Revisit the first problem under chapter 5. Name efficient data-structure and access methods for problems, which can be solved algorithmically.
Q 6.5 : Which spatial index types are supported by spatial DBMS software, e.g. Postgres/postgis, Oracle Spatial, IBM DB2 Spatial Extender, MS SQL Server-Spatial extension, Google Earth, etc.? Use articles in Encyclopedia of GIS and web resources to support your answer. Are there any surprises (e.g. use of 1-dimensional structures)? Why?
Q 6.6 : Discuss the following pithy statement: Decision to use a spatial index for geographic queries (e.g. point, range, nearest neighbor) taking unreasonably long time in a DBMS is far more important than choice of spatial-index-types, e.g. R-tree, Grid-file, 2D-tree, BSP-tree. For simplicity consider point datasets in Euclidean space. Do you agree? Briefly justify your answer using 100 words or less.
Q 6.7 : Compare alternative binary-valued raster structures (e.g. Region Quad-tree, run length encoding, and Freeman chain coding) using the the following criteria and test cases:
1. Which raster structures lead to simpler (and more efficient) algorithms for
  - area and perimeter estimation for regions
  - geometric set union, intersection, and complement
  - local focal, and zonal operations (Table 4.1, pp. 152)
  - vectorization (section 5.3, pp. 207-211)
2. Classify these raster structres into lossy or lossless compression schemes.
3. What storage compression ratio is achieved for three raster datasets in Figure 4.12 (pp. 147)? Assume that white cells have a value of 0 and non-white cells have a value of 1 despite varying grayscale.
4. Identify spatial auto-correlation value ranges (e.g. zero, negative, positive, non-negative, non-positive), where the compression methods are effective. Are geographic dataset likely to exhibit spatial auto-correlation value in that range ?

Chapter 7: Architectures

Q 7.1 : Define interoperability and modularity. Why are these properties of interest to an organizing acquiring software such as GIS? List specific business use cases to motivate each property.
Q 7.2 : Compare and contrast syntactic and semantic barriers to interoperability. Define and illustrate each each barrier. Which barrier to interoperability is addressed by standards and transfer formats? Briefly justify your answer.
Q 7.3 : Which architecture may be preferred by following applications:
1. A volunter digitizing aerial imagery at a disaster site (e.g. Haiti)
2. A fleet owner tracking locations of her vehicles.
3. End-to-end package (location) tracking for delivery companies such as Fedex.
4. Emergency operation center for a large event such as Haiti Earthquake
Q 7.4 : Which architectures are supported by software systems, e.g. ESRI Arc family, Postgres/postgis, Oracle Spatial, IBM DB2 Spatial Extender, MS SQL Server-Spatial extension, Google Earth, etc.? Use articles in Encyclopedia of GIS and web resources to support your answer. Are there any surprises (e.g. use of centralized architures)? Why?
Q 7.5 : Match the items across following lists of system categories and applications:
- Categories: pervasive/ubiquitous computing, mobile computing, context-aware computing, location-aware computing.
- Applications: desktop computers, laptops, tablets, rfid, 1990s cell-phones, E911, Carputer , personal navigation assistant, smart dust , Amazon.com personalizing search results based on past searches, Computer software automatically adjusting clocks for daylight saving without access to central servers such as GPS, Wearable computer ,
Q 7.6 : Consider the taxonomy of location-sensing techniques in Figure 7.18 with categories of active-proximity, active-triangulation, passive-motion-tracking and passive-scene-analysis. Classify the following location-sensing technologies into these categories: global positioning system, rfid, GSM mobile phone tracking , Active Bat , distress radiobeacon , flight data recorder and maritime distress safety system .
Q 7.7 : What privacy concerns are raised in LBS? Also review an industry document with LBS guidelines and best practice. Briefly critique the pros and cons of the proposed approach based on user notice and consent. Limit answer to 500 words.
Q 7.8 : Compare and contrast location privacy with the anonymity supported by services like
Tor anonymity networks .
Q 7.8 : How should LBS privacy concerns be balanced with the following:
1. Geo-Location , which is used to infer geographic location of Internet entities (e.g. laptops, workstation, servers) for fighting (financial0 crimes, regional licensing, geo-targetting, fraud detection, spam fighting, etc.
2. Enhanced 911 to locate cell-phones and deliver assistance during 911 calls.
3. Social check-in offered by social networking services such as foursquare , facebook, etc.

Chapter 8: Interfaces

Q 8.1 : Briefly describe cartography with core ideas, e.g. simplification, classification, cartogrgaphic generalization, and symbolization. Which of these capabilities are used in popular web-based mapping services such as Google Map, mapquest, Google Earth, etc.?
Q 8.2 : Briefly describe Geovisualization with novel possibilities (e.g. interactive feedback, animation, 3D, non-visual displays) relative to paper based maps and cartography. Which of these capabilities are used in popular web-based mapping services such as Google Map, mapquest, Google Earth, etc.? Propose possible use-cases for presently unused capabilities of Geovisualization.
Q 8.3 : Briefly describe usability engineering and representative usability measures. Propose a couple of user tasks (e.g. those from Table 8.5, pp. 318) and compare usability of following web-based mapping services: Mapquest Maps , Google Maps , and Bing Maps .
Q 8.4 : Review the notion of LineDrive maps from Rendering Effective Route Maps: Improving Usability Through Generalization . Compare and contrast LineDrive maps with route maps provided by common web-services (e.g. mapquest, Google Map) for driving under normal conditions as well as unusual conditions (e.g. unpredictable traffic congestions). Use Figure 14 in the Siggraph 2001 paper to illustrate your answer if appropriate.
Q 8.5 : Review maps of your university campus. Which cartographic and geovisualization ideas are used there? Propose possible use-cases for presently unused core ideas of cartography and Geovisualization. Also propose a few benchmark user tasks (e.g. find Keller Hall) and evaluate usability of web-based campus map using measures suggested in the textbook.
Q 8.6 : Compare the catographic aspects (e.g. generalization, abstraction and visual variables such as position, size, orientation, shape, color hue/saturation/value, texture, focus and arrangement) of the following:
1. Maps generated by > Google Maps
2. Various illustrations in wikipedia article on Cartography
3. Illustrations in wikipedia article on Cartogram
4. Illustrations in article on Napolean
5. Napoleon march to Moscow: map 1 , map 2
Q 8.7 : Compare the set of geovisualization ideas (e.g. animation, 3D, non-visual displays, interaction / feedback ) used by the following:
1. Illustration in web-page for Geovisualization Tools Development at National Cancer Institute.
2. 2004 Indonesian Tsunami
3. Illustrations in wikipedia article on Topography
4. Time maps
5. Illustrations in wikipedia article on Pictorial Maps
6. Q 8.8 : Maps have been created to support a variety of tasks such as orientation, localization, navigation, etc. Review the article on Orienteering Map and identify cartographic details to support navigation.

Chapter 9: Spatial Reasoning and Unertainty

Case study with notion 100-year flood using public articles.

Uncertainty cuts across many topics covered so far in the course. Explore this statement by identifying specific examples of issues uncertainty raises for chapters 2 to 8:
1. Chapter 2: Relational Databases: Which qualitative uncertainty model (e.g. possible worlds, beliefs/knowledge, 3-valued logic, fuzzy sets, rough sets) are supported by SQL ?
2. Chapter 3: Mathematical Models Which properties of fuzzy sets differ from those of probabilities? See slide 34 for a summary of properties of fuzzy sets.
3. Chapter 4: Spatial Data Models (Field, Object): What data-types and operations may be provided by a SQL3 library to represent uncertainty in scalars (e.g. temperature forecast) as well as locations of points, line-strings and polygons ?
4. Chapter 5: Algorithms Consider a future database supporting fuzzy regions (slide 35-36). Determine the computational complexity of and propose an algorithm for detemining fuzzy membership of a point for a given fuzzy region.
5. Chapter 6: Storage Structures Propose representations, data-structures, and storage structures for fuzzy regions to detemine fuzzy membership of points in fuzzy regions.
6. Chapter 7: Architecture: Which type of imperfection (e.g. error, imprecision, vagueness) is used by local anonymizers location-privacy ?
7. Chapter 8: Interface: What visual representations convey location uncertainty in gps-location, gps-trajectory or flood-plain polygon ?
Compare and contrast:
1. Belief vs. Knowledge
2. Proability vs. Possibility vs. Plausibility
3. Error vs. granularity
4. uncertainty vs. vagueness
5. possible worlds vs. default reasoning
6. Bayes' rule vs. Demspter-Shafer theory of evidence
Which data quality dimensions (e.g. accuracy, bias, completeness, consistency, currency, format, granularity, lineage, precision, reliability, timeliness) are supported by the following:
1. US National Map Accuracy Standard
2. GPS Receiver Accuracy
3. National Academies' reports on Mapping the Zone: Improving Flood Map Accuracy (2009).
Emergency planners face many uncertainties in planning evacuation routes. These include uncertainties in number and location of evacuees as well as uncertainties in available capacities in transportation networks. Which qualitative approaches (e.g. possible world, belief/knowledge, default reasoning, 3-valued logic, fuzzy sets) are used by Emergency planner to cope with such uncertainties ?
Which information issues from section 9.2 (e.g. uncertainty, vagueness, granularity, data quality dimensions) are relevant to the following:
1. news article and video-clip titled I-Team: Old Maps Flooding Homeowners With Problems , Nov. 2010.
2. Star Tribune article titled Minnesotans uninsured and underwater , Nov. 24th, 2010.
3. Wikipedia entry on Flood insurance and 100-year flood
Which GIS uncertainty sources (e.g. specifications, measurements, transformations) from section 9.2.3 are relevant to the following:
1. Article authored by M. Werner with title Uncertainty in Flood Extent Estimation due to Uncertain Parameters
2. National Academies reports on Mapping the Zone: Improving Flood Map Accuracy (2009) and Elevation Data for Floodplain Mapping (2007).
Which quantitative approaches to uncertainty from section 9.2 (e.g. probability, Bayesian probability, Demster-Shafer theory of evidence) is used in the following:
1. slides titled Impact of DEM Uncertainties on Flood Maps in context of coastal zones of Portugal
2. USGS article on Updating Flood Inundation Maps Efficiently: Building on Existing Hydraulic Information and Modern Elevation Data with a GIS

Chapter 10: Time

Motivating example:
- Spatial and Spatio-temporal Data Mining
- Space-Time Modeling and Analysis Workshop Videos , e.g. Time Geography by Prof. Shih-Lung Shaw.
Time cuts across many topics covered so far in the course. Explore this statement by identifying specific examples of issues time raises for ideas discussed in chapters 2 to 8:
1. Chapter 2: Relational Databases:
  - Which temporal data-types (e.g. time-point, time-interval, time-series) and operations are supported by relational databases (e.g. SQL) ?
  - Temporal database literature explored extensions of relational databases. Review chapter 10.2 to compare the contrast the following pairs: (a) transansaction-time and valid-time (b) tuple timestamping and attribute time-stamping
  - Consider a gps tracking device, which computes position (i.e. latitude, longitude) every minute. However, the device communicates to a remote database server every five minutes. Assume that the device sends all computed positions and communication time and database update time are negligible. Construct instances of a bi-temporal table with columns of device-id and position for tuple-timestamping as well as attribute-timestamping. Limit gps-tracking information to a ten-minute period, with two devices each with two synchronized communication events. (Hint: Tables 10.2 and 103., pp. 370 provide examples of tuple-timestamping and attribute timstamping.)
2. Chapter 3: Mathematical Models:
  - List the major concepts proposed in chapter 10.1 to model spatio-temporal information such as history of land-use (e.g. Fig. 10.5, pp. 365).
  - Which branches of mathematics are appropriate for modeling spatio-temporal phenomena such as
    1. spatial time-series data
    2. trajectories of moving objects
    3. spatial networks (e.g. roadmaps) with time-varying properties (e.g. travel-time for an edge) ?
    4. mobile device: What temperature and temperature gradient will a mobile sensor register ? How would its readings related to those of stationary sensors ? Consider a weather front, which may be stationary or moving.
3. Chapter 4: Spatial Data Models (Field, Object):
  - What data-types and operations may be provided by a SQL3 library to represent spatio-temporal data-types such as trajectories of moving points, time-series of measurements at various locations, etc. ?
  - Which spatio-temporal data-types and operations are suggested in chapter 10.1, pp. 361-367 ?
4. Chapter 5: Representations and Algorithms:
  1. What challenges spatio-temporal data and queries pose for spatial representations such as spagetti, node-arc-area, raster, TIN, networks, etc.? Consider data-sets such spatial time-series, trajectories of moving objects, transportation networks with time-varying properties (e.g. speed), etc.
  2. What challenges spatio-temporal data and queries pose for algorithms methods ? Consider problems such as the following:
    1. Determine nearest gas station for a mobile user driving on a freeway
    2. Determine shortest paths on scheduled public-transportation (e.g. bus, train, flights) networks for a stationary user
    3. Identify pairs of land and ocean location with high correlated climate change events (e.g. effect of El Nino)
    4. Retrieve trajectory pairs within 500 feet at a common timepoint
    5. Identify flocks of vehicles given a set of trajectories
5. Chapter 6: Storage Structures
  - What challenges spatio-temporal data and queries pose for storage and indexing methods such as R-tree across stationary platforms (e.g. workstations, servers) and mobile platforms (e.g. cell-phones, gps-devices). You may consider queries listed in in previous sub-part on chapter 5.
  - Review the temporal storage structures described in chapter 10.4 to compare and contrast the following pairs: (a) B-tree and overlapping B-tree; (b) overlapping B-tree and Multi-version B-tree; (c) Multi-version B-tree and Segment-tree; (d) Segment-tree and R-tree; (e) R-tree and Historic R-tree
6. Chapter 7: Architecture: How do mobile devices and users impact software and hardware architectures ? What are the differences in location-privacy (or authentication) issues across stationary and moving persons?
7. Chapter 8: Interface:
  - Consider the visualization in Figure 10.11 (pp. 374) in section 10.3.2 for the bi-temporal spatial representation of the construction of a bypass during years of 1993, 1994 and 1995. Do you find it intuitive? Does it help users understand changes in highway network (and recorded database state)? How can cartographic ideas (e.g. map symbolization, visual variables, chapter 8.2, pp. 301-305) help improve this visualization ? How can geo-visualization ideas (e.g. animation, 3D, feedback, section 8.3, pp. 306-316) help ? Would you prefer separation of visualization along transaction-time from that along valid-time ?
  - Compare and contrast interfaces for mobile GIS environments (e.g. cell-phone, gps devices) and stationary environments (e.g. workstations, geo-video-walls)?
  - In stationary environments, what visual representations are suitable for communicating spatio-temporal information, e.g. change in ice-cover over decades, trajectory of a vehicle over a year, etc. ?
8. Chapter 9: Uncertainty:
  - Consider a weather report suggesting that there is a 50 percent chance of rain in a city C on a future day D. Which of the following interpretation are reasonable?
    1. Temporal A: It will rain everywhere inside C for half of day D.
    2. Temporal B: It will rain somewhere inside C for half of day D.
    3. Spatial A: It will rain over half the area of city C all day during day D.
    4. Spatial B: It will rain over half the area of city C sometime during day D.
    5. Model: Half the prediction models suggest that it will rain somewhere inside city C sometime during day D.
    6. Scenario: Half the scenarios (e.g. boundary conditions) explored by a prediction model suggests that it will rain somewhere inside city C sometime during day D.
    Propose new vocabulory to reduce ambiguities by distinguishing between these interpreation. (Hint: For an accuracy based approach, see the paper titled Modeling uncertainty in spatiotemporal objects by T. Shokri, M. Delavar, M. Malekl and A. Frank in International Symposium on Spatial Accuracy Assessment in Natural Resources and Environmental Sciences, 2006. This paper decomposes total uncertainty into spatial uncertainty, temporal uncertainty, attribute uncertainty, logical uncertainty, and completeness uncertainty. Are these adequate to distinguish between the cases listed above ?
  - Another perspective on spatio-temporal uncertainty in context of gps-tracks is provided in the paper titled Visualization of Spatio-Temporal GPS Uncertainty within a GIS Environment by S. K. Lodha et al, Proc. SPIE, 2002. This paper introduces notions of horizontal error, vertical error, speed error, and direction error. Compare and contrast these with the notions of spatial uncertainty, temporal uncertainty, attribute uncertainty, logical uncertainty, and completeness uncertainty in the paper by T. Shokri, A. Frank et al. ?
  - What visual representations convey spatio-temporal uncertainty in gps-location, gps-trajectory or flood-plain polygon ? (Hint: A set of visual representation for gps-trajectory uncertainty are proposed in the paper by S. K. Lodha et al. It proposes diffused blobs for horizontal position error and pie-slice glyphs for speed and direction errors. Figure 5 on ast page illutrates these representation.). Evaluate these visual representations for gps tasks such as navigation, location based services, orientation, localization, precision targeting, etc. Which alternative visual representations would you recommend in context of specific tasks listed earlier? How would you extend these visual representation to depict other uncertainties related to vertical error, spatial uncertainty, temporal uncertainty and other types of uncertainties?
  - Representative spatio-temporal statistical methods are explored in following papers:
    1. C. K. Wikle, Spatio-Temporal Methods In Climatology, Encyclopedia of Life Support Systems , EOLSS Publishers, UNESCO, 2002.
    2. E. Crema, A probabilistic framework for assessing spatio-temporal point patterns in the archaeological record , Journal of Archaeological Science, 37(5), May 2010, Elsevier, Pages 1118-1130.
    What do these methods compare to those in spatial statistics ?