# 4 - Geometric 4 Flashcards

What is the finding line segment intersections problem?

- Given a set of h horizontal and v vertical line segments in a plane
- find all intersections

What is the naive approach?

- Brute force - check all pairs
- Each pair can be checked in O(1) time
- never better than O(hv)

- No algorithm better than O(hv) in worst case - could be hv intersections

What is the solution to the line segment intersections problem?

- When number of intersections p is small we use the line-sweep technique
- Will have O(n log n + p) in worst case, where n = h + v

What is the line-sweep technique?

- Imagine infinite vertical line ‘sweeping’ left to right across the plane
- Sweep hits each vertical line once, hits each horizontal line at its left end point and leaves at its right end point

How do perform line sweep? 1/2

- Set up a list of end points - each vertical line is represented once - each horizontal line is represented twice, by its left and right end points
- sort the list by x-coord
- assume that no two horizontal lines intersect, and no two vertical line intersects

How do perform line sweep? 2/2

- Simulate line sweep by ‘processing’ list of endpoints
- Maintain throughout a set of candidate horizontal lines - those whose left end point has been processed but right end point has not
- When a vertical line is encountered, consider only candidate lines for intersections
- Gives real speed up in many cases
- But could still have as many as hv comparisons and few (even zero) intersections
- all horizontal lines could be candidates throughout the sweep

Sorting line endpoints

- Sort list by xcoord
- if two or more have same xcoord, break ties so that:
- a horizontal line’s left end point always comes before a vertical line end point which in turn always comes before a horizontal line’s right end point

How to represent candidate set so when a vertical is reached, don’t have to compare it with all candidates?

- Refer to ycoord of a candidate as its value
- If current vertical has endpoints (x, y1) and (x, y2) we want to find all candidates with value in range y1 .. y2
- We should represent candidate set so it facilitates range searching
- Also need to perform insertions and deletions efficiently

Using an array for efficient range searching

- Search is O(log h) where array size is at most h
- scan is O(k) if there are k items in range
- Insertion / deletion are no better than O(h) in worst case
- Is there an alternative?

What is an AVL tree?

- Balanced binary search tree
- For each node, heights of left and right subtrees differ by most 1 tree with h nodes has height O(log h)
- Search, insertion and deletion are all O(log h)

Using an AVL tree for range searching

- Search, insert and delete are O(log h)
- Range searching is O(k + log h)

Algorithm for range searching

- Assume we are searching for elements in range min .. max
- Partial traverse of tree at a given node
- if value max ignore right branch but explore left (if any)
- otherwise include value and explore both branches

Analysis of range searching with AVL tree

- Let k be number of elements in S in the range min .. max and let s = |S|
- Algorithm is O(k + log s) - k nodes visited with value in range
- visit at most 1 node to left of range, and 1 node to right of range, at each level, O(log s) levels

Data structures required

/** Class representing a binary tree where each node * has a value and a possible left subtree and a * possible right subtree */ public class Tree { public int val; public Tree leftSubtree; // null if no left subtree public Tree rightSubtree; // null if no right subtree } /** Class representing a set of integers */ public class IntSet { public ArrayList intSet; }

What is the range searching algorithm for AVL trees (code?)

/** Input: an AVL tree t containing integer values, and * minimum and maximum range values min and max * Output: the set of values in t between min and max */ public IntSet rangeSearch (Tree t, int min, int max){ if (t==null) return ; else { int y = t.val; Tree lt = t.leftSubtree; Tree rt = t.rightSubtree; if (y ≥ min && y max) return rangeSearch(lt,min,max) {y} rangeSearch(rt,min,max); else if (y