geosearch.ppt - Computer Science Department at Princeton University.ppt.ppt

Geometric Algorithms Geometric search: Overview Types of data. Points, lines, planes, polygons, circles, ... This lecture. Sets of N objects. Geometric problems extend to higher dimensions. Good algorithms also extend to higher dimensions. Curse of dimensionality. Basic problems. Range searching. Nearest neighbor. Finding intersections of geometric objects. 1D Range Search Extension to symbol-table ADT with comparable keys. Insert key-value pair. Search for key k. How many records have keys between k1 and k2? Iterate over all records with keys between k1 and k2. Application: database queries. Geometric intuition. Keys are point on a line. How many points in a given interval? 1D Range Search Implementations Range search. How many records have keys between k1 and k2? Ordered array. Slow insert, binary search for k1 and k2 to find range. Hash table. No reasonable algorithm (key order lost in hash). BST. In each node x, maintain number of nodes in tree rooted at x. Search for smallest element ? k1 and largest element ? k2. 2D Orthogonal Range Search Extension to symbol-table ADT with 2D keys. Insert a 2D key. Search for a 2D key. Range search: find all keys that lie in a 2D range? Range count: how many keys lie in a 2D range? Applications: networking, circuit design, databases. Geometric interpretation. Keys are point in the plane. Find all points in a given h-v rectangle? 2D Orhtogonal Range Search: Grid Implementation Grid implementation. [Sedgewick 3.18] Divide space into M-by-M grid of squares. Create linked list for each square. Use 2D array to directly access relevant square. Insert: insert (x, y) into corresponding grid square. Range search: examine only those grid squares that could have points in the rectangle. 2D Orthogonal Range Search: Grid Implementation Costs Space-time tradeoff. Space: M2 + N. Time: 1 + N / M2 per grid cell examined on average. Choose grid square size to tune performance. Too small: wastes space. T