A hard problem and an easy problem
Feb. 9th, 2013 05:17 pmVarious edits several hours later.
So the other day Jeff told me an open problem regarding 3-dimensional polytopes[0]. (Note: All polyhedra considered here are assumed to be convex.)
Essentially, the question is, if a polyhedron has a large number of vertices, does it have to have a 2-dimensional projection with a large number of vertices[3]? More formally, given k, does there exist n such that any polyhedron with at least n vertices must have some projection with at least k vertices?
To phrase it another way, we can define f(n) = min_{polyhedra P with at most n vertices} max_{projections Q of P} (vertices of Q). Then the question is, does f(n) go to infinity, or is it bounded? If we want a polyhedron with a large number of vertices, does some projection have to have a large number of vertices? Or is there some finite C such that is it possible to get polyhedra with arbitrarily many vertices but with each projection having at most C vertices? A sort of geometric Ramsey theory thing, basically.
It seems to me that if you don't even try, and take an n-vertex approximation to the sphere (i.e. space your vertices as evenly as possible), the result ought to have about Θ(√n) on its largest projection (probably about √(πn), to be specific), so I guess that's an upper bound on f(n), but that's not very interesting, because that's what you get if you don't even try. (Not that that's the worst you can do -- you can easily do much worse if you try to fail. It's easy to get n-1, and I think you can get n, at least if n is even. But again, that's pretty dumb; there isn't really much interesting about that.)
So here's something annoying I noticed about this problem yesterday: The "take all the projections" operation (however we formalize it) doesn't seem to be preserved under combinatorial equivalence.
Take a regular octahedron. None of its projections are triangles. But if you take one face and make it way larger than the other sides, now you've got a triangle projection.
(Btw, note that the regular octahedron, though consisting of 6 vertices spaced as evenly as possible, actually has a projection using all 6 vertices!)
I don't know -- maybe some more limited version of this operation is preserved under combinatorial equivalence. (Like, say, "What's the most vertices in a projection", which is what we care about.) But it sure seems like tackling this problem is going to require getting one's hands dirty with some actual geometry. (OK, it almost certainly would regardless. But this definitely makes it work.)
That was the hard problem. Here's the easy problem. It's not really related, but my brain sort of drew a connection from it to something I was thinking about regarding the hard problem the other day. (The only real relation was that they both involved certain angles being acute.) You know those old multi-display billboards, that are cut into strips? Each of which is actually a triangular prism, so it can rotate between three states? Why do they use triangles? Well, OK, that's pretty easy; it's so that the strips don't run into each other as they turn. But... do they not run into each other? OK, obviously, they don't, or the signs wouldn't work. But why mathematically don't they run into each other?
Yes, this is easy. Still, it wasn't something I'd really thought about before, so I don't know, I thought it was kind of neat.
-Harry
[0]Annoying terminological footnote. The word "polytope" is just the general word for polygon, polyhedron, etc., in any number of dimensions. So if I'm just talking about 3-dimensional ones -- you know, what we usually call polyhedra -- why did I use the word polytope? Well, unfortunately the people who actually study these things use the words slightly differently. They use "polyhedron" to mean something in any number of dimensions, the difference from a polytope being that polyhedra are allowed to be unbounded. In any case, here I've already specified that I'm talking about your usual 3-dimensional convex bounded polyhedra, so I'm going to call them "polyhedra" from here on.
[3]Because, you know, if you project a polyhedron onto a plane, you get a polygon.
So the other day Jeff told me an open problem regarding 3-dimensional polytopes[0]. (Note: All polyhedra considered here are assumed to be convex.)
Essentially, the question is, if a polyhedron has a large number of vertices, does it have to have a 2-dimensional projection with a large number of vertices[3]? More formally, given k, does there exist n such that any polyhedron with at least n vertices must have some projection with at least k vertices?
To phrase it another way, we can define f(n) = min_{polyhedra P with at most n vertices} max_{projections Q of P} (vertices of Q). Then the question is, does f(n) go to infinity, or is it bounded? If we want a polyhedron with a large number of vertices, does some projection have to have a large number of vertices? Or is there some finite C such that is it possible to get polyhedra with arbitrarily many vertices but with each projection having at most C vertices? A sort of geometric Ramsey theory thing, basically.
It seems to me that if you don't even try, and take an n-vertex approximation to the sphere (i.e. space your vertices as evenly as possible), the result ought to have about Θ(√n) on its largest projection (probably about √(πn), to be specific), so I guess that's an upper bound on f(n), but that's not very interesting, because that's what you get if you don't even try. (Not that that's the worst you can do -- you can easily do much worse if you try to fail. It's easy to get n-1, and I think you can get n, at least if n is even. But again, that's pretty dumb; there isn't really much interesting about that.)
So here's something annoying I noticed about this problem yesterday: The "take all the projections" operation (however we formalize it) doesn't seem to be preserved under combinatorial equivalence.
Take a regular octahedron. None of its projections are triangles. But if you take one face and make it way larger than the other sides, now you've got a triangle projection.
(Btw, note that the regular octahedron, though consisting of 6 vertices spaced as evenly as possible, actually has a projection using all 6 vertices!)
I don't know -- maybe some more limited version of this operation is preserved under combinatorial equivalence. (Like, say, "What's the most vertices in a projection", which is what we care about.) But it sure seems like tackling this problem is going to require getting one's hands dirty with some actual geometry. (OK, it almost certainly would regardless. But this definitely makes it work.)
That was the hard problem. Here's the easy problem. It's not really related, but my brain sort of drew a connection from it to something I was thinking about regarding the hard problem the other day. (The only real relation was that they both involved certain angles being acute.) You know those old multi-display billboards, that are cut into strips? Each of which is actually a triangular prism, so it can rotate between three states? Why do they use triangles? Well, OK, that's pretty easy; it's so that the strips don't run into each other as they turn. But... do they not run into each other? OK, obviously, they don't, or the signs wouldn't work. But why mathematically don't they run into each other?
Yes, this is easy. Still, it wasn't something I'd really thought about before, so I don't know, I thought it was kind of neat.
-Harry
[0]Annoying terminological footnote. The word "polytope" is just the general word for polygon, polyhedron, etc., in any number of dimensions. So if I'm just talking about 3-dimensional ones -- you know, what we usually call polyhedra -- why did I use the word polytope? Well, unfortunately the people who actually study these things use the words slightly differently. They use "polyhedron" to mean something in any number of dimensions, the difference from a polytope being that polyhedra are allowed to be unbounded. In any case, here I've already specified that I'm talking about your usual 3-dimensional convex bounded polyhedra, so I'm going to call them "polyhedra" from here on.
[3]Because, you know, if you project a polyhedron onto a plane, you get a polygon.
