“Orphans” are things you meant to think about but which you’ve regretfully concluded are never going to rise to the top of the stack. Ideas you never finished having.
Blogging your orphans seems a good use of a math blog, or even a partial math blog like this one — at best, someone else will be able to tell you what’s interesting about your question, or even derive some interest from it themselves; and at worst, someone will be able to explain to you why your question is in fact not interesting, thus setting your mind at ease.
Anyway: the mention of Voronoi cells reminded me of a question that once vexed me about combinatorial geometry in R^2. The question actually arose from an article I wrote about Howard Rosenthal and Keith Poole, political scientists who use data from Congressional votes to map legislators onto low-dimensional Euclidean space. But their method doesn’t really specify points in R^n. When n = 1, for instance, what they get is not a set of 535 points on the real line, but an ordering of the 535 legislators along an axis representing liberalism at one end and conservatism at the other.
What’s really being recorded by the projection of Congress to R^2? I think it’s something like this — for each triple of legislators (x,y,z) you ask: is z to the left or the right of the ray that starts at x and proceeds towards y?
There are n! possible orderings of n points on the line. How many “orderings” are there of n points in the plane?
An algebraic combinatorist might phrase the question like this: Let M be a 3xn matrix with real entries, where the third column consists entirely of 1’s. Suppose every 3×3 minor of M is nonsingular. Then let f(M) be a function from the set of 3-tuples of distinct elements of [1..n] to the set {+1,-1}, where you assign to each 3-tuple (i,j,k) with i < j < k the sign of the determinant of the 3×3 matrix formed by rows i,j,k of M.
Question: As M ranges over 3xn matrices of the given form, how many different functions f(M) are there?
An obvious upper bound is 2^(n choose 3), but this is way too big. Note that if you replace “3” by “2”, the answer to the analogous question is n!.
As a geometer, I’d phrase the question in a different (but I think equivalent) way:
Question: Let X_n be the space of ordered n-tuples of points in R^2 such that no three points are collinear. How many components does X_n have?
Again, if you replace R^2 with R^1 and “no three points are collinear” with “no two points coincide,” you get n!.
Let a(n) be the answer to the questions above (which, if I am not confused, have the same answer.) Then a(3) = 2 and a(4) = 14, and I think maybe a(5) is 252 but I’m not really sure. Combinatorial geometers with a soft spot for orphans, tell me more!
Quomodocumque 
This feels like a question about VC dimension. (Not that that answers it!)
Looks like an Euler characteristic problem to me. You have forgetful maps from X_{n+1} to X_n which are fibrations and the preimage of a set {x_1…x_n} consists of all those points not colinear with the given n. This is the complement of the set of lines through n generic points. The number of path components of said is a classical Euler characteristic calculation that I can’t remember off the top of my head.
Ah, here we go: the number of components in the complement of the lines through m generic points is (m^4 – 2m^3 + 3m^2 – 2m + 8)/8. (The number in the complement of n generic lines is n(n+1)/2 + 1.)
So the number of components should be the product of these as m goes from 1 to n.
argh. OK, my bad; the number of components in the complement of lines through m points is m(m+1)/2 + 1, not the first number I listed.
I’ll stop now.
Wait, where did you get these numbers? I just doodled this out on paper and it seems to me that the number of components in the complement of the lines through m generic points should be quartic in m, as in comment 3, not quadratic, as in comment 4. In particular, I think when you draw 4 points there are 18 regions, which doesn’t agree with comment 4.
In fact, I worked out the quartic — it is
(1/8)*(n^4-6*n^3+23*n^2-26*n+8)
and plugging in the first few values 1,2,7,18,41… one indeed finds it in the Encyclopedia of Integer Sequences as sequence A055503. (Sorry, don’t know how to include links in comments.)
So I guess that the a(n) should be the product of the first n terms of this sequence, something which grows sort of like (n!)^4.
Now go blog your own orphan!
I have debated whether to return to the scene of this, because I cannot explain just what I was thinking. The formulas involving lines through m generic points are just outright wrong in both comments 3 and 4, as you point out.
I like the idea of blogging orphaned problems, and perhaps if I get around to having a blog that will appear.
[…] looking at a seating problem (ménages problem). At Quomodocumque we read about a leftover problem: n points in the plane with no 3 collinear. Brent of Math Less Traveled calculates Pi through looking at the integer part of its multiples, […]
I got here via the Carnival of Mathematics; I think http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/ordertypes/ and http://www.research.att.com/~njas/sequences/A063666 have some answers for your question.
Marvelous! For those not following the links, there’s a paper of Aichholzer, Aurenhammer, and Krasser which computes what (if I understand correctly) is the number of orbits of the natural S_n-action on the components of X_n, for n = 1, .. 11. Apparently these components go by the name “order types” and were invented by Goodman and Pollack in a paper on “multidimensional sorting.”
It’s worth adding, I think, that the number of order types is singly-exponential in n (upper and lower bounded by functions of the form c^n for some constant c) while if the points are labeled (you don’t mod out by the natural S_n-action) it’s going to be within a singly-exponential factor of n!. So counting order types rather than labeled order types gives much smaller (but still big) numbers.
Oops, never mind that, I was thinking of something else that’s singly exponential. I don’t know offhand what the asymptotic number of order types looks like. Though I think there’s something about this in Knuth’s book Axioms And Hulls.