The inherent catch is that we prefer a cartesian system, hence we'll always prefer a compatible coverage if the costs are similar.

I don't disagree. My point is that without knowing anything qualitative about the data set it's going to be difficult to determine if the costs are similar.

Remember that the OP wanted to preselect (spatial index) plausible candidates, how would you do this with circles?

Not sure what you mean here. The exclusion by circles should be as simple as this:

#!/usr/bin/env perl 
use strict;
use warnings;

my @circles = (
    {
        x => 3.0,
        y => 10.0,
        r => 5.0
    },
    {
        x => 4.0,
        y => 9.0,
        r => 2.0
    },
    {
        x => 12.0,
        y => 4.0,
        r => 4.0
    },
);

while (my $one = shift @circles) {
    for my $other (@circles) {
        my $dx2 = ($one->{x} - $other->{x}) ** 2;
        my $dy2 = ($one->{y} - $other->{y}) ** 2;
        my $r2  = ($one->{r} + $other->{r}) ** 2;
        if ($dx2 + $dy2 < $r2) {
            warn "Potential overlap: $one->{x}, $one->{y}, $one->{r} w
+ith $other->{x}, $other->{y}, $other->{r}\n";
        }
    }
}
[download]