In their setting, they had an image and wanted to "squish" away "unimportant" parts during the resize, while maintaining the remaining image information. Their solution was to find "seams" in the image. A seam is a path between opposite edges of an image, using any combination of straight or diagonal moves (in this way, a seam is a "contiguous" strand of pixels but need not be simply a row or column). Their approach was to use a dynamic programming algorithm to find a seam whose removal would cause the least "disturbance" in an image.

Here, your solution could be even easier. You have an "image" made up of "." and non-"." pixels. You want to find and remove any horizontal or vertical seams made up of entirely "." pixels. This can also be done in a simple dynamic programming way.

#!/usr/bin/perl
use strict;

chomp( my @data = <DATA> );
$_ = [ split // ] for @data;

do {
  print_map(\@data);
  print "=====\n";
} while (remove_vert_seam(\@data));

sub remove_vert_seam {
    my $data = shift;
    my $seam;

    my $rows = $#$data;
    my $cols = $#{ $data[0] };
 
    for my $j (0 .. $cols) {
        $seam->[0][$j] = 0 if $data->[0][$j] eq ".";
    }

    # there is a seam from the top row to ($i,$j)
    # only if (i,j) has a "." and there is a seam from
    # the top row to any of (i-1,j-1), (i-1,j), (i-1,j+1)

    # if there is a seam, remember its predecessor so we
    # can trace it back.

    for my $i (1 .. $rows) {
    for my $j (0 .. $cols) {
        if ($data->[$i][$j] eq ".") {
            $seam->[$i][$j] = $j-1
                if $j-1 >= 0     and defined $seam->[$i-1][$j-1];
            $seam->[$i][$j] = $j
                if                   defined $seam->[$i-1][$j];
            $seam->[$i][$j] = $j+1
                if $j+1 <= $cols and defined $seam->[$i-1][$j+1];
        }
    }
    }

    # if there is a seam to the bottom row, trace it back
    # to the top and remove all of the cells that are visited

    for my $j (0 .. $cols) {
        if (defined $seam->[$rows][$j]) {
            my $i = $rows;
            while ($i >= 0) {
                splice @{ $data->[$i] }, $j, 1;
                ($i,$j) = ($i-1, $seam->[$i][$j]);            
            }
            return 1;
        }
    }
    return 0;
}

sub print_map {
    my $data = shift;
    for (@$data) {
        print join("", @$_), $/;
    }
}

__DATA__
XX...
X....
.....
....X
...XX
[download]

XX...
X....
.....
....X
...XX
=====
XX..
X...
....
...X
..XX
=====
XX.
X..
...
..X
.XX
=====
XX
X.
..
.X
XX
=====
[download]

If you applied the same approach and then went on to remove horizontal seams, you would get

XX              XX.
XX  instead of  X.X
XX              .XX
[download]

XX:..
X:...
:....
....X
...XX
=====
XX:.
X:..
:...
...X
..XX
=====
XX:
X:.
:..
..X
.XX
=====
[download]

Update: another example:

XXX:..........XX
XXXX:....XX:...X
X:.....XXX:..XXX
XX:.....XXXX:.XX
XXXXXXX.........
[download]

XXX:.......XX
XXXX:..XX:..X
X:...XXX:.XXX
XX:...XXXX:XX
XXXXXXX......
[download]

Essentially, treat the locations as masses connected by damped springs. Then run what amounts to a physics simulation until the masses no longer move or some specified number of iterations is reached.

For a pre-packaged Perl solution, I've used Graph::Layouter to good effect.

For some reason this reminded me of quadtrees. Your "squooshing" would be removing central rows if they don't contain any points. Not a concrete answer but that's what your diagrams brought to mind.

Update: And there seems to be a Algorithm::QuadTree on CPAN that might get you started.