non-overlapping ranges constraint?

Suppose I have a table

  CREATE TABLE range (min int NOT NULL, max int NOT NULL, otherdata TEXT);

I want to make sure that no two tuples in this table describe
overlapping ranges, that is:

  tuple1.min<=tuple2.max AND tuple1.max>=tuple2.min

I arrived at doing the checking using a custom function:

  CREATE FUNCTION range_available(int, int) RETURNS bool AS
  'LOCK TABLE range;
  SELECT count(*)=0 FROM range WHERE min<= $2 AND max>= $1
    AND min != $1 AND max != $2;
  ' LANGUAGE 'sql';

  ALTER TABLE range ADD CONSTRAINT check_range
    CHECK (range_available(min, max));

This solves the probelm at hand but I have severe performance
problems. Inserts/deletes on the table are rare, as are modifications
to min and max, but the table is subject to mass-updates touching
otherdata and it appears that the check constraint is executed even
if neither min nor max are modified. Basically this turns updating
into an O(n^2) operation, as neither min<= $2 nor max >= $1
are particularly selective.

My question is whether there is a more elegant solution; since the
problem is essentially a geometric one, perhaps people storing
geometric objects know a generic solution? Additional fact:
in the "real" problem both min and max are of type timestamp.

Best regards
--
Helge Bahmann <bahmann@math.tu-freiberg.de>             /| \__
Network admin, systems programmer                      /_|____\
                                                     _/\ |   __)
$ ./configure                                        \\ \|__/__|
checking whether build environment is sane... yes     \\/___/ |
checking for AIX... no (we already did this)            |