کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649667 1342462 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Counting polycubes without the dimensionality curse
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Counting polycubes without the dimensionality curse
چکیده انگلیسی

dd-dimensional polycubes are the generalization of planar polyominoes to higher dimensions. That is, a dd-D polycube of size nn is a connected set of nn cells of a dd-dimensional hypercubic lattice, where connectivity is through (d−1)(d−1)-dimensional faces of the cells. Computing Ad(n)Ad(n), the number of distinct dd-dimensional polycubes of size nn, is a long-standing elusive problem in discrete geometry. In a previous work we described the generalization from two to higher dimensions of a polyomino-counting algorithm of Redelmeier [D.H. Redelmeier, Counting polyominoes: Yet another attack, Discrete Math. 36 (1981) 191–203]. The main deficiency of the algorithm is that it keeps the entire set of cells that appear in any possible polycube in memory at all times. Thus, the amount of required memory grows exponentially with the dimension. In this paper we present an improved version of the same method, whose order of memory consumption is a (very low) polynomial   in both nn and dd. We also describe how we parallelized the algorithm and ran it through the Internet on dozens of computers simultaneously.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4576–4583
نویسندگان
, ,