Suppose $n$ disjoint points, some red and some blue, are organized on a line. We want to partition the line to two subsets, one containing all the red points and one containing all the blue points. How many connected components will be in the division?
The answer depends on the arrangement. If the points are arranged like:
R R R R ... R R R R B B B B ... B B B B
then two components are needed, but if they are arranged like:
R B R B R B R B ... R B R B R B R B R B
then $n$ components are needed, and this is obviously the worst case.
My question is: when the $n$ points are arranged in a square, instead of on a line - what is the worst-case number of connected components required?
For simplicity, let's assume that the points are in "general position", i.e, no point is on the square boundary, no two points coincide, no three points are colinear, etc.