Algorithm that finds concise representations of sets of pairs using Cartesian products I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it.

Suppose as an input you have a list of two-dimensional data points (xi, yi). Your goal is to "simplify" this data by providing an output that is equivalent to the input, but grouped together using structures like this: ({x1, x2, .., xn}, {y1, y2, .., ym}), which denotes a set of all (xa, yb) where a ∈ {1, 2, .., n} and b ∈ {1, 2, .., m}. A perfect result is to have as few of these structures + remaining data points as possible.

Some points to consider:


The output can be a combination of simple data points and such
structures.
The structures in the output should be mutually
exclusive.
It may as well be that there is no way to simplify a given
input.


Example 1:

Input: (1, 1), (1, 2), (2, 1), (2, 2), (4, 5) Output: ({1, 2}, {1, 2}), (4, 5)

Example 2:

Input: (1, 1), (1, 2), (1, 3), (4, 5) Output: ({1}, {1, 2, 3}), (4, 5)

Example 3:

Input: (1, 2), (2, 2), (3, 2), (2, 1), (2, 3) Output: ({1, 2, 3}, {2}), ({2}, {1, 3})
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.