looking for suggestions to detect collisions in a java.awt.Graphics2D plane

I am writing an agent-based simulation in Java and I am looking for 
suggestions on how I can detect collisions between my critters as they 
move about on a two-dimensional plane.  These critters simulate living 
things (people perhaps) all continuously moving about, but no two of 
them should be able to occupy the same space at the same time.

I have a way to detect collisions which works okay for small N, but the 
required computation is N-squared, it increases with the square of the 
number of critters, and I want to find better.

Let me describe more specifically:  The GUI is being drawn with Java 
Swing.  Each critter is circle shaped, a java.awt.geom.Area constructed 
with a java.awt.geom.Ellipse2D, and 15 pixels in diameter.  In each 
increment of time in the simulation each critter can move some distance 
in some random direction.

To compute the move for each critter first I create the proposed Area 
that will be occupied if the move succeeds without collision, by calling 
the Area method createTransformedArea(AffineTransform).  Then I test to 
see if the proposed Area is already occupied by any other critter's Area 
by looping through the other critters, subtracting each critter's area 
from the proposed area (with the Area.subtract() method).  If the 
proposed area is not changed by this subtraction then there is no 
collision, and the proposed move is allowed.  That works but it is 
N-squared.

So I am looking for suggestions.

One wishful idea I've had is to look at the color of the pixels in the 
proposed Area.  The background in my simulation is all white, but the 
Critters and other things are non-white.  So a proposed Area would be 
allowed if it was all white.  But I don't know the way to learn that. 
Can someone tell me that?

Thanks very much,
Rich Hammer
Hillsborough
<http://richard-o-hammer.org/firm.model.html>