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]

> Not sure what you mean here.

you are suggesting > n**2/2 comparisons, ie 50m for 10k polygons ... that's - sorry - insane.

Preordering can eliminate most of the fruitless ones.

See my first reply.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}