Are there always two circles that together surround or intersect all points in the following scenario?

125 Views Asked by At

Consider $N$ points in $\mathbb{R}^2$ and $\binom{N}{2}$ circles, one for each pair of points such that it intersects both. Is it always possible to pick two of these circles that together surround or intersect all $N$ points?

Context:

I am studying constraints on causality relations on causal diamonds scattered in 1 time and 2 spacial dimensions. This comes from a special case where the receiving points of all causal diamonds are planar.

1

There are 1 best solutions below

1
On

The answer is No and here is a counterexample:

enter image description here

Just kidding. The above is clearly messy. Let me show the counterexample with $3$ circles at a time:

enter image description here

The blue points (p1 to p3) make an equilateral triangle and are the points which are furthest from each other. The dashed curves show the limits within which other points may be placed (if a point was outside these curves, the blue points would no longer be the points furthest from each other). The circles G1, B1 and R1 connect the blue points. The red points (p4 to p6) are subsidiary points and lie just outside the mentioned circles.

enter image description here

The above circles pass through a blue point and the red point which is furthest from it.

enter image description here

The above circles pass through a blue point and the red point second furthest from it.

enter image description here

Finally, the above circles pass through the red points. Three other circles are possible (those passing through a blue point and its nearest red point) but they are not relevant.

Summing up, we have the following points in the following circles:

$G1 = (p1, p3, p4), B1 = (p1, p2, p5), R1 = (p2, p3, p6)$ $G2 = (p3, p4, p5), B2 = (p1, p5, p6), R2 = (p2, p4, p6)$

The other circles are not relevant as they only contain two points. So, can we combine any two of the circles above so they cover all six points?

The answer is No and so we have a counterexample.