Course Websites

Subject offerings of new and developing areas of knowledge in computer science intended to augment the existing curriculum. See Class Schedule or departmental course information for topics and prerequisites. Course Information: May be repeated in the same or separate terms if topics vary.

Topic: This course is about data structures in computational geometry. Many geometric problems can be viewed as generalizations of standard one-dimensional searching. We will discuss fundamental techniques and recent theoretical developments for basic problems such as point location, orthogonal and nonorthogonal range searching, dynamic convex hulls, and approximate nearest neighbors. We will also explore geometric data structures in a variety of settings, from the word RAM model to computational models inspired by big data, including external memory and streaming. Prerequisite: an undergraduate algorithms course.