# Territories from observations

I have a number of animal observations, and want to deduce the number of territories (i.e. the number of individual animals) from this.

More formally, the problem can be stated as follows: Each observation is a triple consisting of two coordinates and a date. Observations on the same date are assumed to be different animals, whereas observations in close proximity but on different dates might come from the same animal.

I'm looking for the minimal number of territories which can explain all of these observations. Each territory is assumed to be a circle, whose radius is known in advance and the same for all territories. An observation can be assigned to a territory if it falls within that circle, but two observations made on the same date must not be assigned to the same territory. In this model, territories may overlap. An observation may lie within one circle and still be assigned to a different one inside which it lies as well.

Is there an established procedure or algorithm to answer this kind of question? If so, is it an exact optimal solution or an approximation? Do you know of any R package to perform this kind of computation?

At the end of the day, it would also be nice to know which observations have been assigned to the same territory. I believe that with the above definition, this assignment is not uniquely defined in most cases. I'd be also interested in established procedures to make a decision among these alternatives.

If you know of techniques to address this general kind of question, i.e. identifying territories, but the assumptions are different from those stated above, I'd still value a comment providing a useful name or reference.

• Sounds like set cover to me. Jul 31 '13 at 10:52
• @Anony-Mousse: It is a bit like set cover, yes. But the number of possible sets may be huge, so listing all of them will probably be infeasible. I guess vertex coloring might be the better analogy, with egdes for pairs if they are from the same day or too far apart. Yesterday I thought this modelling would break since the diameter of the convex hull need not equal the diameter of an enclosing circle, but today I'm not so sure, and this might in fact work out. Still thinking…
– MvG
Jul 31 '13 at 11:01
• How big is your data? Oh, and the proximity you mentioned above is not transitive, that will become a problem. So say A near B near C, A and C at day 1, B at day 2. A ~ B, B ~ C, but A !~ C with your definition. Jul 31 '13 at 13:10
• You may be interested in topological data analysis to solve this problem; perhaps persistent homology. statweb.stanford.edu/~susan/talks/AIMTopDA.pdf Aug 6 '15 at 17:34