How do I check if cartesian coordinates make up a rectangle efficiently?

Ситуация следующая:

• Есть N массивов.
• В каждом массиве (0..N-1) есть (x, y) кортежи (декартовы координаты) сохранены
• Длина каждого массива может быть разной

Я хочу извлечь подмножество комбинаций координат, которые составляют полную retangle of size N. In other words; all the cartesian coordinates are adjacent to each other.

Example:

findRectangles({
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)},
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)}
})

yields the following:

[(1,1),(1,2),(2,1),(2,2)],
..., 
...(other solutions)...

No two points can come from the same set.

I first just calculated the cartesian product, but this quickly becomes infeasible (my use-case at the moment has 18 arrays of points with each array roughly containing 10 different coordinates).