Space-Efficient Data Structures for Polyominoes and Bar Graphs

Abstract

We provide a compact data structure for representing polyominoes that supports neighborhood and visibility queries. Neighborhood queries concern reporting adjacent cells to a given cell, and visibility queries determine whether a straight line can be drawn within the polyomino that connects two specified cells. For an arbitrary small $\epsilon >0$, our data structure can encode a polyomino with $n$ cells in $(3+\epsilon )n+o(n)$ bits while supporting all queries in constant time. The space complexity can be improved to $3n+o(n)$, while supporting neighborhood queries in $\mathcal{O}(1)$ and visibility queries in $\mathcal{O}(t(n))$ for any arbitrary $t(n)\in \omega (1)$. Previous attempts at enumerating polyominoes have indicated that at least $2.00091n-o(n)$ bits are required to differentiate between distinct polyominoes, which shows our data structure is compact. In addition, we introduce a succinct data structure tailored for bar graphs, a specific subclass of polyominoes resembling histograms. We demonstrate that a bar graph comprising $n$ cells can be encoded using only $n+o(n)$ bits, enabling constant-time query processing. Meanwhile, $n-1$ bits are necessary to represent any bar graph, proving our data structure is succinct.

21 pages, 7 figures