Some friends of mine believe that “search” has been solved. They explain that they can almost always find what they are looking for, and quickly, using keyword search. My life is much more frustrating! There are all sorts of things I look for and can’t find. An additional source of frustration is that I don’t know when to give up, when to conclude that what I’m looking for isn’t there.

Recently I had this experience with a question I thought would make a good blog challenge:

### Does there exist a polyhedron such that **all** of its faces are nonconvex?

**all**

If you can think up a proof or example, please post your answer in the comments section, but with “Spoiler alert:” at its start. If you find an answer through a web search, give us the URL and tell us your search strategy. A URL pointing to discussion of this exact question would also be acceptable, even if the discussion doesn’t provide an answer.

I’d like to give a prize, and thought about various prizes (a Tcho chocolate bar? treating the winner to coffee? …) but decided in true blog spirit to ask for suggestions for an appropriate prize.

P.S. I thought about defining terms such as “polyhedron” and “nonconvex” here. But since this is a search and/or geometry challenge, any readers who do not know the meaning of these 3D geometry terms can still participate. I would be particularly delighted if someone who did not understand the question initially was able to find a solution.

**Update**: An answer has been found. Congratulations, Francine. However I realize I mixed up two searches, and this one isn’t as hard as I thought I remembered.

Daniel Tunkelangsays:Spoiler alert: http://en.wikipedia.org/wiki/List_of_uniform_polyhedra#Other_nonconvex_forms_with_nonconvex_faces

Daniel Tunkelangsays:In return, here’s another challenge:

What’s the most efficient algorithm for sorting a partially ordered set S given only a comparator that allows you to compare 2 elements in S? The comparator tells you, in constant time, which of two distinct elements is greater, or if the two are incomparable.

Gene Golovchinskysays:I also found the same list as Daniel with the query “polyhedron faces are nonconvex?” which returned several wikipedia articles that I examined in order. The fourth-ranked hit (a part of the third-ranked page) seems to have the answer.

I am willing to collect Daniel’s chocolate for him.

Gene Golovchinskysays:Some potential answers to Daniels’s question: ITLB + o(ITLB) + O(n) and LB + o(LB) + O(n) but I don’t claim to understand whether the answer is actually correct, or even if it is an answer to Daniel’s question.

I ran the query “most efficient algorithm for sorting a partially ordered set” and looked at a few results near the top.

Eleanor Rieffelsays:Daniel,

Nope! That page doesn’t provide an answer to the question I asked. I want a polyhedron such that ALL faces are nonconvex, not just some. While the URL you give provides a number of examples in which SOME of the faces are not convex, they all have at least one face that is convex (for example, a triangle).

So give it another try!

—Eleanor

Eleanor Rieffelsays:Gene,

I believe your “fourth-ranked hit (a part of the third-ranked page)” points to the same page that Daniel gives. I had found that page early on in my web searching also. As I explained in the comment to Daniel, unfortunately it doesn’t answer the question I posed.

—Eleanor

Francinesays:Here’s something close.

I found a page in a book that stated that in a ‘Szilassi torus’ all faces are nonconvex by searching for ‘polyhedron “all faces are nonconvex”.

Looking up what a Szilassi torus is, a wikipedia article had a drawing that looked promising and I sent the two links to Eleanor.

http://en.wikipedia.org/wiki/Szilassi_polyhedron

Eleanor pointed me to an exploded view of the faces: http://mathworld.wolfram.com/SzilassiPolyhedron.html

and pointed out that one of the faces is convex. This puzzled me since the book said that “all faces are nonconvex”.

I then noticed that the polyhedron on the wolfram page (in the upper left) can be rotated . By rotating the polyhedron, there was one convex face on the “inside” of the torus.

Here’s another applet where the convex face is bright green and easier to see:

http://www.drking.plus.com/hexagons/szilassi/index.html

jeremysays:Ah, I think I understand the question a little better now. It’s not just that the polyhedron is nonconvex in 3 dimensions. It’s that every face of the polyhedron also has to be nonconvex, in 2 dimensions.

After speaking with Eleanor, I understand now that this isn’t just a search challenge, in that she knows the answer and is trying to see if one of us can find the information she knows about. Rather, she honestly doesn’t know whether or not one of these polyhedrons (polyhedra?) exists. Part of the difficulty of this search task comes in figuring out when you can stop, because you’re confident that such information does not exist, or when you should keep going, because you just haven’t come up with the correct way to query for it.

Eleanor Rieffelsays:Francine,

That’s a cool example, and closer than anything I found. It has only one convex face. (Most of what I thought about, or saw, had symmetries that meant that if there was one convex face, then there were many.) Plus you found a discussion of the problem,so even though it your search didn’t fully answer the question, you definitely get a prize! Let me know if you’d like a Tcho chocolate bar, to be treated to coffee, or something else!

More prizes to be award to anyone who can reduce the number of convex faces from one to zero!

Eleanor Rieffelsays:Jeremy – Thanks for clarifying both the geometric and search aspect of the question!

Francinesays:There’s more than one solution! (verified by Eleanor) Look at Figure 2 on page 3 of this document.

I found it by first trying a metasearch engine with the query from my previous post that had netted only the one result and got nothing. So I tried Ask.com (more variety with different search engines) with the more general query ‘polyhedron “nonconvex faces”‘ and followed the link for the 4th result, which sounded promising: “Isohedra with nonconvex faces” and then searched for nonconvex within the article and saw the figures in Figure 2.

Eleanor Rieffelsays:Francine,

That’s great! These examples are cool!

I feel I should have come up with the top right one in Figure 2. I thought about squishing a cube, but didn’t quite see this way of doing it. I like it because it is so attractively simple. The others are neat too.

From your search techniques, I have learned that I should try metasearch engines.

I’ll be bringing some chocolate by your office tomorrow!

—Eleanor

FXPAL Blog » Blog Archive » A challenge for searchsays:[…] FXPAL Blog On technology and beyond! « Search and/or geometry challenge! […]

Eleanor Rieffelsays:Actually, I’m embarrassed to say that I confused two searches, and that this one isn’t hard after all – Grunbaum’s paper “Isohedra with nonconvex faces” comes up in the first page of the search for “polyhedron nonconvex faces” on Google for instance.

What I remembered is a search where I got links to all sorts of folding papers which was not the sort of reconstruction I was interested in. That must have been for a search about reconstruction of polyhedra, which is closer to the actual thrust of my work. I think on this one, it was an interrupted search. I remember doing a search before lunch some day last week, and looking through the polyhedra on the page Daniel and Gene found, and looking through a couple sites.

After lunch I worked on a different projects and only came back to the reconstruction work a day or two later, but didn’t look back at this problem. A few days later, I met with some folks to chat about geometric reconstruction who are much more expert than I am, and during the conversation remembered this problem. I got intrigued when they didn’t know the answer off the top of their heads, but it wasn’t in the direct line of what I needed to figure out for the reconstruction project, so I was trying not to think about it. I’d been planning to give a puzzle I know the answer to as a “teaser” for an in-house talk I’m giving on Friday, but switched to this one.

To avoid embarrassing myself, I should have tried the search again, instead of relying on my poor memory. Oh well! If you don’t embarrass yourself in blog posts every once in a while, you must not be posting enough! It did work wonderfully as a teaser, since I had great conversations about geometry with a number of people, particularly Francine.

Gene Golovchinskysays:“Not hard at all” is not quite right, since several people were not able to recognize the relevant document (or at least didn’t report that they had).

Perhaps if we had tools that represented our search history more effectively, it would have been easier (and therefore more natural) for you to revisit your search session prior to blogging about it.