Skip to main content
Springer Nature Link
Log in

Counting d-Dimensional Polycubes and Nonrectangular Planar Polyominoes

  • Conference paper
Computing and Combinatorics (COCOON 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4112))

Included in the following conference series:

Abstract

A planar polyomino of size n is an edge-connected set of n squares on a rectangular 2-D lattice. Similarly, a d-dimensional polycube (for d ≥2) of size n is a connected set of n hypercubes on an orthogonal d-dimensional lattice, where two hypercubes are neighbors if they share a (d–1)-dimensional face. There are also two-dimensional polyominoes that lie on a triangular or hexagonal lattice. In this paper we describe a generalization of Redelmeier’s algorithm for counting two-dimensional rectangular polyominoes [Re81], which counts all the above types of polyominoes. For example, our program computed the number of distinct 3-D polycubes of size 18. To the best of our knowledge, this is the first tabulation of this value.

Work on this paper by the second author has been supported in part by the European FP6 Network of Excellence Grant 506766 (AIM@SHAPE).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Broadbent, S.R., Hammersley, J.M.: Percolation processes: I. Crystals and mazes. Proc. Cambridge Philosophical Society 53, 629–641 (1957)

    Article  MATH  MathSciNet  Google Scholar 

  2. The online encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences

  3. Jensen, I.: Enumerations of lattice animals and trees. J. of Statistical Physics 102, 865–881 (2001)

    Article  MATH  Google Scholar 

  4. Jensen, I.: Counting polyominoes: A parallel implementation for cluster computing. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Gorbachev, Y.E., Dongarra, J., Zomaya, A.Y. (eds.) ICCS 2003. LNCS, vol. 2659, pp. 203–212. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  5. Lunnon, W.F.: Counting polyominoes. In: Atkin, A.O.L., Birch, B.J. (eds.) Comp. in Number Theory, pp. 347–372. Academic Press, London (1971)

    Google Scholar 

  6. Lunnon, W.F.: Counting hexagonal and triangular polyominoes. In: Read, R.C. (ed.) Graph Theory and Comp., pp. 87–100. Academic Press, New York (1972)

    Google Scholar 

  7. Lunnon, W.F.: Symmetry of cubical and general polyominoes. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 101–108. Academic Press, New York (1972)

    Google Scholar 

  8. Lunnon, W.F.: Counting multidimensional polyominoes. The Computer Journal 18, 366–367 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  9. Martin, J.L.: Computer techniques for evaluating lattice constants. In: Domb, C., Green, M.S. (eds.) Phase Transitions and Critical Phenomena, vol. 3, pp. 97–112. Academic Press, London (1974)

    Google Scholar 

  10. Redelmeier, D.H.: Counting polyominoes: Yet another attack. Discrete Mathematics 36, 191–203 (1981)

    MATH  MathSciNet  Google Scholar 

  11. Sykes, M.F., Gaunt, D.S., Glen, M.: Percolation processes in three dimensions. J. of Physics, A: Math. and General 10, 1705–1712 (1976)

    Article  Google Scholar 

  12. Vöge, M., Guttmann, A.J.: On the number of hexagonal polyominoes. Theoretical Computer Science 307, 433–453 (2003)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Technion—Israel Institute of Technology, Haifa, 32000, Israel

    Gadi Aleksandrowicz & Gill Barequet

Authors
  1. Gadi Aleksandrowicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gill Barequet
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, University of Notre Dame, IN 46556, Notre Dame, USA

    Danny Z. Chen

  2. Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan

    D. T. Lee

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Aleksandrowicz, G., Barequet, G. (2006). Counting d-Dimensional Polycubes and Nonrectangular Planar Polyominoes. In: Chen, D.Z., Lee, D.T. (eds) Computing and Combinatorics. COCOON 2006. Lecture Notes in Computer Science, vol 4112. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11809678_44

Download citation

  • DOI: https://doi.org/10.1007/11809678_44

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-36925-7

  • Online ISBN: 978-3-540-36926-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation