Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings

Compressed indexing is a powerful technique that enables efficient querying over data stored in compressed form, significantly reducing memory usage and often accelerating computation. While extensive progress has been made for one-dimensional strings, many real-world datasets (such as images, maps, and adjacency matrices) are inherently two-dimensional. Unfortunately, naively applying 1D techniques to 2D data leads to suboptimal results, as fundamental structural repetition is lost during linearization. This motivates the development of native 2D compressed indexing methods that preserve both compression and query efficiency.