דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Counting polycubes without the dimensionality curse
event speaker icon
גדי אלכסנדרוביץ' (מדעי המחשב, הטכניון)
event date icon
יום ראשון, 11.5.2008, 13:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
$d$-dimensional polycubes are the generalization of planar polyominoes to higher dimensions. That is, a $d$-D polycube of size $n$ is a connected set of $n$ cells (hypercubes) of an orthogonal $d$-dimensional lattice, where connectivity is through $(d-1)$-dimensional faces of the cells. Computing $A_d(n)$, the number of distinct $d$-dimensional polycubes of size $n$, 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. 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 talk we present a method whose order of memory consumption is a (very low) \emph{polynomial} in both $n$ and $d$. Furthermore, we parallelized the algorithm and ran in thropugh the Internet on dozens of computers simultaneously. This enables us to find $A_d(n)$ for values of $d$ and $n$ far beyond any previous attempt.

Joint work with Gill Barequet (Computer Science, Technion)
[בחזרה לאינדקס האירועים]