How to determine area of MKMapRect with greatest concentration of MKAnnotation objects?

Question

Given an MKMapView that contains a variable amount of annotations ([mapView annotations]) at various points on the map and the MKMapRect value MKMapRectWorld, how can I determine an area on the map that has the greatest concentration on MKAnnotation objects (perhaps the 5-15 annotations closest to one another) ?

Example scenarios:

* Coffee finder: Determine which area of the map has the most Starbucks

* K9 statistics: Determine which area of the map has the most Cocker Spaniels

The "area" could be a set rect size or determined by a block of annotations, I don't necessarily care. Thanks for your help!

Answer 1

You will find related question helpful.

Also take look at K-means_algorithm

K-means_algorithm

If you have N annotations and want to break into K parts you can find center (which will fill certain criteria. e.g. minimize the within-cluster sum of squares ) of each of K parts with K-means-algorithm. Once you have center find out distance between center and annotation farthest from center it will give radius of region you are interested. There are several variations of K-means_algorithm, you can choose whichever based on performance and ease of implementation.

EDIT: I have not implemented following, but think will definitely give one of solution

If you are OK with range 5-10, there can be multiple solutions. So we will find one of solution.

1- Say you have (N=100) annotations and want which (P =15) of them are most located densely.

2- Then we will divide N annotations in K = N/P groups(here K = 7) randomly

3- Use K-means algorithm so that finally we will have K groups that can be differentiated as separate entities.

4- These K groups will have property of minimum " within-cluster sum of squares".

5- If you want to save computational time, you can relax definition of most concentrated group as minimum "within-cluster sum of squares" as opposed to area bounded by them.

6- select a group from obtained K group that satisfies your criteria.

7- If want to persist to minimum area(greatest concentration) definition then you will need to do lots of computation

a. First determine boundary annotations of given group, which itself a huge problem.

b. calculate are of each polygon and see which is least. not complicated but computationally demanding)

EDIT2:

I tried whatever I can and finally thought it this question belongs to specialist math website. I asked your question here and from the answer , you can get paper discussing this problem and solution here. Problem they discuss is given N points, find the K points whose area of convex hull is minimum.