Computer Graphics-related Tasks Involving The "Smallest-circle problem"

Question

I have two tasks related to the "Smallest-circle problem":

1. Implement a one-pass algorithm that calculates an enclosing circle for a generic set of 2D points.
2. Define a set of 2D points Q for the algorithm, which returns an enclosing circle bigger than the minimum one.

I've done task #1 using Welzl's algorithm; but I'm not sure I understood the second question. Are they asking me to find a way for the algorithm to break, or a limitation of the algorithm?

Answer 1

The first task isn't asking for an algorithm to find the smallest enclosing circle, it's asking for an algorithm to find an enclosing circle. It specifies that this should be a "one-pass" algorithm, meaning that the algorithm iterates only once over the list of points.

There are many possible answers to the first task, because it doesn't put any limit on how big you're allowed to make the circle; for example, if the set contains only a single point, it would be completely valid for the algorithm to find a circle of radius 10²⁰ that includes that point. (Of course, there's no reason to go so extreme. If the radius of the smallest enclosing circle is R, there's a very simple one-pass algorithm to find an enclosing circle whose radius is at most R√2, which I'll put in a spoiler tag below so that that you can think about it first if you like.)

Iterate over the points, keeping track of the least and greatest x-coordinate and the least and greatest y-coordinate. Return the circle with center = (½(x_min + x_max), ½(y_min + y_max)) and radius = ½√((x_max − x_min)² + (y_max − y_min)²).

The second task depends on your answer to the first task. Since your algorithm presumably does not find the smallest enclosing circle for all sets of points (since we don't know of any one-pass algorithm that does so), the second task is just to find a set of points for which your algorithm returns a larger circle than necessary. For example, if for task #1 you use the algorithm described in the spoiler above, then for task #2 you could give

The set {(1, 0), (0, 1), (-1, 0), (0, -1)}: the smallest enclosing circle has radius 1, but the above algorithm gives a circle of radius √2.