Sign In

Communications of the ACM

ACM News

CMU Scientists Solve 90-Year-Old Geometry Problem

View as: Print Mobile App Share:
In this tiling of the plane by congruent squares, the green and violet squares meet edge-to-edge as do the blue and orange squares.

In geometry, Keller's conjecture is the conjecture that in any tiling of Euclidean space by identical hypercubes, there are two cubes that meet face to face.

Credit: David Eppstein

Carnegie Mellon University computer scientists and mathematicians have resolved the last, stubborn piece of Keller's conjecture, a geometry problem that scientists have puzzled over for 90 years.

By structuring the puzzle as what computer scientists call a satisfiability problem, the researchers put the problem to rest with four months of frenzied computer programming and just 30 minutes of computation using a cluster of computers.

"I was really happy when we solved it, but then I was a little sad that the problem was gone," said John Mackey, a teaching professor in the Computer Science Department (CSD) and Department of Mathematical Sciences who had pursued Keller's conjecture since he was a grad student 30 years ago. "But then I felt happy again. There's just this feeling of satisfaction."


From Carnegie Mellon University School of Computer Science
View Full Article



No entries found