In 1984, Stein and his co-authors posed a problem concerning simple three-dimensional shapes, known as semicrosses, or tripods. By definition, a tripod of order n is formed by a corner and the three adjacent edges of an integer n × n × n cube. How densely can one fill the space with non-overlapping tripods of a given order? In particular, is it possible to fill a constant fraction of the space as tripod order tends to infinity? In this paper, we settle the second question in the negative: the fraction of the space that can be filled with tripods must be infinitely small as the order grows. We also make a step towards the solution of the first question, by improving the currently known asymptotic lower bound on tripod packing density, and by presenting some computational results on low-order packings. © 2006 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)1973-1981
Number of pages9
JournalDiscrete Mathematics
Volume307
Issue number16
DOIs
StatePublished - 28 Jul 2007

    Research areas

  • Regularity lemma, Semicross packing, Tripod packing

ID: 127711126