# 4 - Geometric 4 Flashcards

1
Q

What is the finding line segment intersections problem?

A
• Given a set of h horizontal and v vertical line segments in a plane
• find all intersections
2
Q

What is the naive approach?

A
• 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
3
Q

What is the solution to the line segment intersections problem?

A
• 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
4
Q

What is the line-sweep technique?

A
• 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
5
Q

How do perform line sweep? 1/2

A
• 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
6
Q

How do perform line sweep? 2/2

A
• 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
7
Q

Sorting line endpoints

A
• 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
8
Q

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

A
• 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
9
Q

Using an array for efficient range searching

A
• 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?
10
Q

What is an AVL tree?

A
• 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)
11
Q

Using an AVL tree for range searching

A
• Search, insert and delete are O(log h)
• Range searching is O(k + log h)
12
Q

Algorithm for range searching

A
• 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
13
Q

Analysis of range searching with AVL tree

A
• 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
14
Q

Data structures required

A

/** 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; }

15
Q

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

A

/** 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

16
Q

Summary of line-sweep algorithm

A
• Assume that he (vₑ) denotes the horizontal (vertical) line with endpoint ₑ form list E of endpoints of all lines; sort E on x-coordinate; create empty AVL-tree C of candidates; for (Point2D.Double e : E) if (e is from a horizontal line) if (e is a left endpoint) add e to C; else // e is a right endpoint remove left endpoint of he from C; else // e is from a vertical line { let y1,y2 be y-coords of ve endpoints; range search C for y1..y2; output intersection (ve,hf) for all horizontal lines hf in the range; }
17
Q

Analysis of line-sweep algorithm

A
• Sorting endpoints is O(n log n)
• Sweep encounters 2h + v points
• At each horizontal point, we insert or delete from tree contributing 2h x O(log h) to complexity
• At vertical point i, suppose nᵢ intersections with candidates, total time taken to process vertical points is O(n₁ + log h + n₂ + log h +…+ nᵥ + log h) = O(p + v log h)
18
Q

What is the overall complexity of line-sweep?

A

O(n log n + h log h + v log h + p) = O(n log n + p) since h = O(n) and v = O(n).