2 - Geometric 2

Question 1

How to connect a set of points to form a simple polygon?

Answer 1

• Use a circular scan
• start at a point p (pivot) and connect each points as encountered as you scan over them in a circle

Question 2

What is the problem with a circular scan?

Answer 2

Can have lines between points that cross over regions belonging to other lines (Extend each line out to edge of circular scan to form regions)

Question 3

How to successfully perform circular scan?

Answer 3

• Choose the pivot, p to be a particular point in the input set
  
  • e.g. point with largest x coord

Question 4

When is a circular scan successfull?

Answer 4

When each line resides in its own region in the circle and no line crosses into other regions

Question 5

What is the simplePolygon algorithm?

Answer 5

/** Input: an arbitrary polygon, points, of n points, * i.e., a sequence of n points * Output: points, sorted to give a simple polygon */

public void simplePolygon (PointSet points) {

double num, denom;

double [] angle = new double[points.length];

select_largest_xcoord(points); /* modifies points so that points[0] contains the point with * largest x-coord (and smallest y-coord if a tie) */ for (int i=1; i

Question 6

What is the complexity of the simplePolygon algorithm?

Answer 6

• loop is O(n) where n is number of points
• sort is O(n log n)
• so overall O(n log n)

Question 7

What complication can occur in simplePolygon algorithm?

Answer 7

• If two or more points are collinear with the pivot (points[0])
• If so, further sort these points in increasing order of distance from pivot

Question 8

How can simplePolygon be simplified?

Answer 8

• don’t need to use arctan
  
  • can sort on line gradients don’t need to compute square root to sort on distances

Question 9

What is the convex hull problem?

Answer 9

• convex hull of a set of points is the smallest (total length of edges, or area) possible polygon that contains the points
• given a set P of n points, find their convex hull
• Uses Graham Scan algorithm, O(n log n) time

Question 10

convex hull example

Answer 10

the convex hull doesn’t need to include all points in P 1 2 3 4 4!=24 ways to connect, only 3 give distinct polygons 1234 1243 1324 none are convex 124 (with 3 in middle) gives a convex polygon

Question 11

What are the properties of a convex hull

Answer 11

• Every point of the convex hull of P is itself a member of P
• the points of P with largest/smallest x/y coords are points of the convex hull of P the furthest pair of points in P of the convex hull of P

Question 12

What is the Graham Scan algorithm?

Answer 12

• Choose a point known to be on the hull as pivot – say the point with the largest x coordinate (using the smallest y coordinate to break a tie if necessary)
• Scan the remaining points in order of angle to the pivot
• For each point, include it in temporary hull, possibly excluding one or more of its predecessors

Question 13

How to perform Graham Scan algorithm?

Answer 13

• As we trace out the potential hull, we expect to ‘turn left’ along each point from the pivot point
• If we ‘turn right’ we must exclude one or more points p5 must be excluded because the angle between -p4 — p5- and -p5 — p6- is 180º p4 must be excluded because the angle between -p3 — p4- and -p4 — p6- is 180º need to exclude points that would cause lines to exit polygon boundary, should only be the furthest boundary points

Question 14

What is the Graham Scan algorithm code?

Answer 14

/** Input: an arbitrary polygon p of n points, * i.e., a sequence of n points * Output: q, a simple polygon that is the convex hull * of the points in p */

public PointSet grahamScan(PointSet p) {

simplePolygon(p); // earlier algorithm

PointSet q = new PointSet(p.length);

q[0..2] = p[0..2]; // deep copy

int m = 2;// m points other than pivot in current hull

for (int k = 3; k = Math.PI)

m–; // exclude q[m]

q[++m] = p[k]; // add p[k] to the current hull

}

return q[0..m];

}

Question 15

What is the complexity of Graham Scan?

Answer 15

• Complexity of grahamScan simplePolygon is O(n log n)
• angle function has O(1) complexity - gives the anticlockwise angle between the positive
  
  • direction of - -q[m-1]—q[m]- and the positive direction of -q[m]—p[k]- - in fact only need to know whether angle is - can be implemented without using trig functions Main loop has O(n) complexity (a point is eliminated at most once) - So overall O(n log n) - consequence of sorting
• check this slide

Question 16

What is the furthest pair of points problem/application?

Answer 16

Find the pair of points that are furthest apart

Question 17

What is the naive method of the furthest pair of points problem?

Answer 17

Checking each pair of points - O(n²)

Question 18

What is the faster method for the furthest pair of points problem?

Answer 18

• Let P be a set of points, where n = |P|
• Furthest pair of points in P are points of the convex hull of P
  
  • Convex hull may be constructed in O(n log n) time
  • Furthest pair of points can then be found in O(n) time -
• Overall (n log n) time

Question 19

What is the algorithm for finding the distance between a furthest pair of points in P?

Answer 19

“Rotating calipers” method: 1. Find two points p, q, on the convex hull with minimum and maximum y-coordinate respectively. 2. Draw two horizontal lines (the “calipers”) l1 and l2 through each of p and q, and record the distance d(p, q). 3. Rotate l1 clockwise around p, and rotate l2 clockwise around q, keeping l1 parallel to l2 at all times, until one of the calipers l{l1, l2} reaches the next point (call it r) on the convex hull. 4. Repeat steps 2-3 with caliper l rotated clockwise around the next pivot r and with the other caliper rotated around its old pivot until l1 reaches q and l2 reaches p (half circle). (Note, the perpendicular distance between the calipers may change during the course of their rotation.) 5. Return the largest distance d(p, q) measured at Step 2 as the furthest distance between points on the convex hull.