Sweeps, circles and half-planes

Questions 1 to 5 of 8

1. 1. In rotating calipers, why does the pointer for the far corner only move forward around the hull?

   The pointer is reset to corner 0 for each edge, so it only sees the corners in orderThe hull is sorted by x, so the pointer can only move from left to rightatan2 gives the far corner for each edge, and the pointer only checks the answerGoing counterclockwise, the edge directions turn once through 360 degrees, so each far corner moves forward once per lap and never returns
2. 2. What is the minimum width of the triangle with corners (0, 0), (4, 0) and (0, 3)? Give the decimal value.

   Type a number.

3. 3. An AI tool wrote rotating calipers for the diameter. It starts the pointer at corner 0 and prints a squared diameter of 130 on a 7-point input. The correct value is 146, from the pair (-5, 6) and (0, -5). What is the best diagnosis?

   The squared distances overflow long long, so the code should use doubleThe pointer starts at corner 0, so on the first edge it never advances to the far corner. The fix is to start at corner 1 and let the loop advance itThe output 130 is right, and the expected 146 is a typo in the problemThe minimum width formula should replace the diameter loop
4. 4. In the closest-pair sweep, why can a point be removed from the set for good?

   A point is removed as soon as it is inserted, because the sort already put it in orderA point is removed once it is more than one unit to the left, which is a fixed constantA point is removed once its x distance from the sweep exceeds the current best distance d. The sweep only moves right and best never grows, so the point can never be close enough againA point is removed when its y value passes the middle of the set
5. 5. An AI tool wrote a closest-pair sweep that checks every point in the set for each new point, and skips the y window. What happens?

   The answer stays correct, but the work grows like n squared, so large inputs can time outThe answer is wrong on any input with more than three pointsIt needs a tolerance to stay correct, because the window is missingIt is faster, because the set is smaller than in the sweep