Valentine Convex Sets

26Apr08

Here’s a problem which I was introduced to in 1997 in Halifax, failed miserably to solve (along with some other students), and then mentioned at a bar and got many people very confused last week.

You need to know the definition of a convex set: a set is convex if for each two points u, v in the set, the line segment uv also lies in the set.

Define a set to be valentine convex if for every three points u, v, w in the set, at least one of the three line segments uv, vw, uw also lies in the set.

Warm-up: show that if S, T are convex sets, the set (S union T) is valentine convex.

Real problem: is every valentine convex set the union of two convex sets?

Along with this nerdy post I’ll give a shout-out to Prof. Small who was the one to torture us poor high school kids with the problem.



3 Responses to “Valentine Convex Sets”

  1. 1 kats

    The warm-up doesn’t seem too hard (I guess that’s why it’s a warm-up). For every three points u, v, w in the set (S union T) at least two of them must have come from either S or T, and therefore the line segment connecting them must be in the set.

    For the real problem, I’m guessing you start with two points u,v whose connecting line segment isn’t in the valentine convex set (if such two points don’t exist, then the set is already a convex set and the proof is trivial). For every other point in the valentine convex set, it must connect to either u, v, or both. If it connects to u, put it in set S, and if it connects to v, put it in set T (it may go in both). Now I just have to show S and T are convex. Hmm..

  2. Dave
    Do you assume the set is closed or you ask the question for arbitrary planar sets?

  3. Kudos on the first comment of the new year, Gil!
    You can safely assume that the sets under consideration are closed and bounded (although it would be interesting for me to know if this makes a difference)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: