A 'voronoi diagram' might be what you are looking for.
http://www.donhavey.com/blog/tutorials/tutorial-7-voronoi-diagrams/

Searching for 'vector quantization' may give you some info, too.

There are some algorithms out there for doing cluster analysis.  I have read about them, but have never implemented them myself, so I'm not super confident that this explanation is going to be correct but I'll give it a shot:

The basic idea is that you posit the existence of some number of clusters, N, within the data.  Each cluster is described by a position P and a radius R.  Things that fall inside the circle {P, R} belong to the cluster, things that don't, don't.

The problem then is to establish actual values for P[i] and R[i] for values of i in [0..N-1].

The basic algorithm is that you seed them with arbitrary values (usually random points for the P values and some selected value for R), and then you iteratively adjust the values of P and R until enough of the data is covered by the clusters that you're happy.

In each iteration, you do more or less this:
* loop over all the data points
* for each point, calculate the probability that it belongs to each cluster (more on this later).  Assign it to the cluster for which it has the highest probability of belonging.
* for each cluster, recalculate the cluster's P value as some appropriately weighted average of the positions of the data points that belong to it, and the R value as some appropriately weighted average of the distance of the cluster's data points to the cluster's new center.
* stop when some threshhold of goodness has been reached.  This is often decided as "when an iteration passes and no data points change their cluster assignment status" or on the basis of covering 90% of the data, or whatever.

The bit about calculating the probability that a given data point belongs to a given cluster involves the fundamental assumption that the closer a given point is to a cluster's center, the more likely it is to belong to that cluster.  In practice, you use a gaussian distribution curve that uses the cluster's R value to establish its one-standard-deviation radius as the actual formula for the probability, although I believe that any monotonically declining function (e.g. a linear decay that reaches zero at radius R, 1/R, or anything else like that) should work too.  Gaussian distributions are usually used for cluster analysis because real world data often fits gaussian distributions around the "true" center.

The other wrinkle, which you've probably figured out already, is "how do you know, a-priori, how many clusters to look for?"  There are a couple of ways.  If you don't mind user input, you can just have the user click on perceived cluster centers, then click a "start" button when they've identified them all.  If you want an automatic solution, then usually the above algorithm is tweaked in such a way that R is constrained not to get bigger than some maximum value.  When the algorithm terminates (because no points changed ownership from one iteration to the next), you check to see if enough of the data was covered for you to call it a good solution.  If not, you increase the number of clusters by one and start over.  So more or less you ask "can you cover the data with 1 cluster that's no bigger than R=(whatever)?" And the algorithm comes back and says "Well, here's the best 1 cluster I can find, but only 75% of the data is covered," and you come back and say "no, not good enough.  How about 2 clusters?"  And you go back and forth until you hit your coverage goal.

It sounds like you may have more stringent mathematical restrictions on your solutions, in which case the type of cluster finding that I described may not be appropriate.

The algorithm I outlined is good for situations where you have a who lot of points that fit some hidden distribution and you're trying to recover a more rigorous description of that hidden distribution from the data.  Or in other words, "these points were distributed according to some function f(); use the points to estimate what f() was in the first place."

It's great if you have some a-priori belief that the location of the points fits a model of statistically random scattering around one or more fixed centers.

If that's not your situation, then this algorithm may be essentially meaningless.

Either way, I did code it up today just for fun, so if you want to see the code let me know and I'll post it.

Sadly, the code is too long (at least, when it's well commented it is) to post here.  The forum won't let me.  Can I send it to you somewhere?

My other idea (after looking at your applet), is that you probably can do what you want just with some graph analysis.

The problem seems to me that you get these clusters of related animals that, to the eye, are obviously related but happen to be connected by one extra line to some other obvious cluster.  If you can find and eliminate those extra lines, then the clusters become well separated and are easy to find.

Those extra, single-line connections can be identified (and thus ignored) by determining whether the animals on either end of the connection share any immediate neighbors in the triangulation.  If they do, then the line stays.  If not, then you eliminate it.

After you eliminate the single-line connections, the rest of the graph breaks into clearly distinct clusters, plus single-animal outliers.  To identify the clusters, you would proceed as follows (and in this whole process, you only consider the connections in the triangulation that remain after doing the above stuff):

1. Mark all the animals as "unexamined"
2. Pick an unexamined animal
3. How many connections does it have?
4. if zero, then this animal is an outlier.  Mark it as examined and go to step 6.
5. otherwise, call a recursive graph-walking function to find the set of animals that are properly connected to this one.
6. continue from step 2 so long as there are any unexamined animals.

The recursive graph walking function would take an animal and an arraylist as parameters, and do the following:
1. Add the animal to the arraylist
2. Mark the animal as examined.
3. loop over each of the input animal's connections
4. if the animal on the other end of that connection has NOT been examined, then call the recursive function with that animal and the same list as parameters.

When the recursive function finally exits, the arraylist will contain all the animals that were in that group, and all of them will have been marked as "examined"