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.

  • $\begingroup$ In the two-dimensional case, what do you mean by "components"? $\endgroup$ – Lord Shark the Unknown Sep 23 '18 at 10:47
  • 1
    $\begingroup$ He means connected components. $\endgroup$ – MJD Sep 23 '18 at 12:16

Maybe I'm misunderstanding the question, but it seems to me that if the two sets are discrete, you never need more than two components. In two dimensions you just have so much space to work with.

enter image description here enter image description here

It looks to me like no matter how mixed together the two sets of points are, you can always send out some long skinny tentacles to phagocytize one of the sets and not the other. I think the only way to prevent this would be for the two sets to be infinite and to approach the same limit point or something like that.

You might get something more interesting if you considered components of a lattice or of some other space that is not so strongly self-connected. A square has a lot of connections and you need a lot of constraints if you want to force someone to disconnect it.

(Related pathological example: the lakes of Wada, a partition of the square into three disjoint connected sets whose three boundaries are all identical.)

  • $\begingroup$ +1 for "phagocytize"! :-) $\endgroup$ – joriki Sep 23 '18 at 22:47
  • 1
    $\begingroup$ Thanks, I was very pleased with myself. $\endgroup$ – MJD Sep 23 '18 at 23:58
  • 1
    $\begingroup$ I learned it from our esteemed moderator @AloizioMacedo. $\endgroup$ – MJD Sep 24 '18 at 0:08
  • $\begingroup$ This sounds convincing, but is this a formal proof? $\endgroup$ – Erel Segal-Halevi Sep 24 '18 at 17:16
  • $\begingroup$ No, it's not a formal anything. $\endgroup$ – MJD Sep 24 '18 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.