Algorithm that finds concise representations of sets of pairs using Cartesian products
For a given set $S$ of points, we construct a bipartite graph $B=(X\cup Y,E)$ such that there is an edge $(x,y)\in E$ iff there is a point $(x,y)\in S$.
The biclique decomposition problem asks for the minimum number of bicliques (complete bipartite subgraph) of $B$ whose edges partition the edge set $E$ of $B$. Since a biclique in $B$ corresponds to a structure defined in this problem, an algorithm that solves the biclique composition problem also solves this problem.

Conversely, we can also transform the biclique decomposition problem into this problem as follows. Given a bipartite graph $B=(X\cup Y,E)$, where $X=\{x_1,x_2,\ldots x_p\}$ and $Y=\{y_1,y_2,\ldots y_q\}$, we create a set $S$ of points such that $(x_i,y_j)\in E$ iff there is a point $(i,j)\in S$.
Consequently, the problem is equivalent to the biclique decomposition problem. However, the biclique decomposition problem is NP-hard, and therefore it is unlikely to solve it efficiently on general bipartite graphs.
Note that the problem is equivalent to ``biclique cover'' if the structures are allowed to be overlapped, i.e., a point can be in more than one structure.