Geometric Applications of BSTs

Flashcards for reviewing geometric applications of Binary Search Trees (BSTs), including range search, interval search, and intersection problems.

What are some geometric applications of BSTs?

Intersection of geometric objects in 1 and 2 dimensional spaces. Applications include CAD, games, movies, virtual reality, databases, and GIS.

What is an example application of Orthogonal line segment and rectangle intersection?

Computer Assisted Design (CAD), and CAD for Very Large Scale Integration (VLSI). Useful for checking that wires must not intersect and have some minimum distance between them in electronic chip design.

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

Databases, Geographic information systems (GIS), Games and physic simulations, e.g., via collision detection

What is the naïve solution for intersection of geometric objects?

For each of the object pairs, check if they intersect, resulting in O(n^2) worst-case time complexity.

How can the worst-case time complexity of range search be improved?

By using BSTs

What is the problem definition for 1-Dimensional Range Search?

Given points on the axis and a range (i.e., two points), output the points contained in the range. (Count version): output the number of points contained in the range.

What Dictionary ADT extensions are needed for 1-Dimensional Range Search?

void insert(Key key, Value value), Value Search(Key k), void delete(Key k), List rangeSearch(Key keyLeft, Key keyRight), int rangeCount(Key keyLeft, Key keyRight)

What is the time complexity of rangeCount?

O(log n) time

What is the time complexity of rangeSearch?

O(R + log n) time, where R is the number of keys contained in the range.

What is the problem with Orthogonal Line Segment Intersection?

Given line segments (either horizontal or vertical), find all intersections.

How is the 2D Orthogonal Line Segment Intersection problem reduced to a 1D problem?

Using the Sweep-Line Algorithm, which transforms the 2D problem into a sequence of 1D range search problem instances.

What is the time complexity for Orthogonal Line Segment Intersection?

O(n log n + R), when there are R intersections.

What is the Sweep-line technique?

A common technique for solving geometrical problems such as convex hull, convex object intersection, and Voronoi diagrams.

What's the goal of 1D Interval Search?

Given intervals, determine whether a search interval intersects any of the other intervals

What operations are supported by an Interval Search Tree?

void insert(Key low, Key high, Value value), Value search(Key low, Key high), void delete(Key low, Key high), LinkedList intersects(Key low, Key high)

In Interval Search Tree, what is considered key and what information is stored?

The left endpoint is the BST key, and nodes store the max endpoint in the subtree

What's the first step in inserting into Interval Search Tree?

Insert the new node using low as the BST key

What's the goal of intersectionSingle?

If interval in node intersects (low,high)-interval, return that interval

What is the time complexity for the intersectionSingle operation?

O(log n)

What is the time complexity for the intersection operation?

O(log n)

What is the problem for Orthogonal Rectangle Insertion?

Find all intersections among a set of orthogonal rectangles.

What technique is used to solve Orthogonal Rectangle Insertion effectively?

Sweep-line algorithm, which transforms/reduces the orthogonal rectangle (2D) insertion to 1D interval search problem instances.

What is the worst-case time complexity for Orthogonal Rectangle Insertion?

O((n + R) log n) when there are R intersections.

Why is Orthogonal Rectangle Insertion has extra complexity compared to orthogonal line segment intersection?

due to the interval search tree implementation.

What were the main topics covered?

1-D range search and 1-D interval search, Orthogonal line segment intersection and orthogonal rectangle intersection, Sweep line technique, for reducing n-D problems to (n-1)-D problems