Computational Geometry with Applications in Geographic Information
Systems

Welcome to CS97: Senior Conference! This year's topic will be on computational geometry and algorithms for Geographic Information Systems (GIS). Computational geometry studies problems relating to geometric objects such as points, lines, and polygons. GIS looks at many of the same problems in a geographic context where points can represent fire hydrants, lines can represent roads, and polygons can represent county boundaries. We'll look at some classical computational geometry topics such as convex hulls, line segment intersection, planar point location, Voronoi diagrams, and Delaunay triangulations. Then we will look at some applications in GIS including vector map overlays, nearest neighbor queries, and perhaps surface modeling.

- Analyze and critically discuss research papers in writing and in class
- Formulate and evaluate a hypothesis by proposing, implementing and testing a project
- Relate project to prior research via a review of related literature
- Write a coherent, complete paper describing and evaluating a project
- Orally present a clear and accessible summary of a research work
- Understand the fundamental questions in computational geometry and analyze different solutions to these questions

- Final Presentation schedule is posted.
- Final project guidelines pdf
- Final Projects from 2006 are available for perusal
- Old project ideas from 2006. Some might be good projects this year too.
- Latex style files

WEEK |
DAY |
ANNOUNCEMENTS |
TOPIC & READING |
HOMEWORK |

1 | Jan 22 | Intro | hw1 | |

Jan 24 | Convex Hulls | |||

2 | Jan 29 | hw2 Project1 |
||

Jan 31 | Drop/Add ends (Feb 01) |
Line Intersection, Overlay | ||

3 | Feb 05 | hw3 | ||

Feb 07 | Orthogonal Range Searching | |||

4 | Feb 12 | hw4 | ||

Feb 14 | Planar Point Location | |||

5 | Feb 19 | hw5 | ||

Feb 21 | ||||

6 | Feb 26 | Voronoi Diagrams | hw6 | |

Feb 28 | ||||

7 | Mar 04 | Delaunay Triangulations | hw7 | |

Mar 06 | ||||

Mar 11 |
Spring Break |
|||

Mar 13 |
||||

8 | Mar 18 | TIN Algorithms | hw8 | |

Mar 20 | Project Proposals |
No Reading | ||

9 | Mar 25 | Skip Quadtrees | hw9 | |

Mar 27 | Last day to declare CR/NC or Withdraw with a "W" (Mar 28) |
No Reading | ||

10 | Apr 01 | Linear Clustering | hw10 | |

Apr 03 | Progress Report |
Research for Final Project | ||

11 | Apr 08 | hw11 | ||

Apr 10 | Redistricting in GIS. Connected Components | |||

12 | Apr 15 | Dynamic MST | hw12 | |

Apr 17 | Review Draft |
LCA | ||

13 | Apr 22 | Wrapup | ||

Apr 24 | Review Feedback |
Final Project talks | ||

14 | Apr 29 | Presentations |
||

May 01 | ||||

May 17 |
Final Paper Due |

15% Paper summaries/class participation

15% Paper presentations

15% Mini-Projects/homework

5% Project proposal/Lit Review

10% Rough Draft

10% Reviewer Comments

10% Project Presentation

20% Final Paper

Wikipedia entry for Computational Geometry

Symposium on Computational Geometry (SoCG, or "sausage") proceedings.

Geometry Algorithms

Flatland

Voronoi animation (Thanks Kit)

MSR's Tiled Vectors