4 - Geometric 4

Question 1

What is the finding line segment intersections problem?

Answer 1

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

Question 2

What is the naive approach?

Answer 2

• 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

Question 3

What is the solution to the line segment intersections problem?

Answer 3

• 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

Question 4

What is the line-sweep technique?

Answer 4

• 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

Question 5

How do perform line sweep? 1/2

Answer 5

• 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

Question 6

How do perform line sweep? 2/2

Answer 6

• 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

Question 7

Sorting line endpoints

Answer 7

• 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

Question 8

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

Answer 8

• 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

Question 9

Using an array for efficient range searching

Answer 9

• 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?

Question 10

What is an AVL tree?

Answer 10

• 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)

Question 11

Using an AVL tree for range searching

Answer 11

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

Question 12

Algorithm for range searching

Answer 12

• 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

Question 13

Analysis of range searching with AVL tree

Answer 13

• 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

Question 14

Data structures required

Answer 14

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

Question 15

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

Answer 15

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

Question 16

Summary of line-sweep algorithm

Answer 16

• 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; }

Question 17

Analysis of line-sweep algorithm

Answer 17

• 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)

Question 18

What is the overall complexity of line-sweep?

Answer 18

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