Geometric Applications of BSTs and Skip Lists

Flashcards about Geometric Applications of BSTs and Skip Lists

What are the applications of the intersection of geometric objects in 1 and 2 dimensional spaces?

CAD, games, movies, virtual reality, databases, GIS

What are the applications of 1-D & 2-D range search, 1-D interval search?

Databases, Geographic information systems (GIS), Games and physic simulations

What is the naive solution for intersection of geometric objects (0-D, 1-D & 2-D)?

For each of the object pairs, check if they intersect.

In 2-Dimensional Range Search, what should be the output given points on 2D space, and a 2D range (here, an axis-aligned rectangle)?

output the points contained in the range.

How to extend the Dictionary ADT to 2D keys?

Insert a 2D key, Delete a 2D key, Search for a 2D key, rangeSearch: find all keys that lie in a 2D range, rangeCount: number of keys that lie in a 2D range

How to extend Dictionary ADT to 2D keys via a grid implementation (array analogue)?

Divide space into an M-by-M grid, Create list of points contained in each square, Use 2D array to directly index each square

For √N x √N grid, if points are evenly distributed, what are the space and time complexities for initializing, inserting and range searching?

Initializing the data structure takes N space, Inserting a point takes O(1) time, Range Search also takes O(1) time because 1 point per square

What is the implication of Clustering, which is a common behavior in geometric (& other) data?

Lists for some square are too long.

Rather than dividing the space evenly into squares, in what other ways can you divide?

Into two halfspaces (not necessarily even sized), Into four squares (even sized), Into two regions

How to construct a 2D Tree?

Recursively partition plane into two halfplanes. Create 2D tree at same time.

How to find all points in a query axis-aligned rectangle in 2D-Tree Range Search?

Check if root point is in the query rectangle. Check left/bottom recursively (if rectangle extends into that part). Check right/above recursively (if rectangle extends into that part)

How to find closest point to query point in 2D-Tree Nearest Neighbor?

Check distance from point 1 to query point. If left/bottom could contain a closer point, recurse left. If right/top could contain a closer point, recurse right

What are KD Trees?

Extension of 2D trees to more dimensions

How to construct Quadtree?

Recursively partition plane into four squares. Each square holds up to some s points, s >= 2 . Any square that has more points is split up into four subsquares. Tree structure follows the partition structure.

What are the usages of Quadtree?

Compression of images. Check connected components in image (image processing)

What is the main idea behind Skip lists?

Multiple layers of linked lists

What does Skip lists contains?

Layer 1: Bottom layer & a simple linked list. Layer 2: Each element of layer 1 is in layer 2 with proba p. Layer 3: Each element of layer 2 is in layer 3 with proba p

What are the steps for deletion example in Skip Lists?

find(28), then remove node and relink

What are the steps for insertion example in Skip Lists?

find(29), then add node to layer 1 (bottom) list. Flip a coin with probability p. If tails, add node to layer 2 list Repeat for layer 3, …

How to achieve O(log n) time for Indexing: access i-th element in Skip Lists?

Add the width of the link

What are some applications of skip lists?

MemSQL, Discord, RocksDB