# 2 - Geometric 2 Flashcards

1
Q

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

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

What is the problem with a circular scan?

A

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)

3
Q

How to successfully perform circular scan?

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

When is a circular scan successfull?

A

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

5
Q

What is the simplePolygon algorithm?

A

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

6
Q

What is the complexity of the simplePolygon algorithm?

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

What complication can occur in simplePolygon algorithm?

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

How can simplePolygon be simplified?

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

What is the convex hull problem?

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

convex hull example

A

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

11
Q

What are the properties of a convex hull

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

What is the Graham Scan algorithm?

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

How to perform Graham Scan algorithm?

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

What is the Graham Scan algorithm code?

A

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

}

15
Q

What is the complexity of Graham Scan?

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

What is the furthest pair of points problem/application?

A

Find the pair of points that are furthest apart

17
Q

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

A

Checking each pair of points - O(n2)

18
Q

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

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

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

A

“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.

20
Q
A