Thread: Finding an evenly distributed subset of geolocations

Hello,

First of all, apologies if this is in the incorrect forum - I really could't decide what this problem falls under. I am a Computer Scientist and by no stretch of the imagination a competent mathematician, so if I could have some guidance with my mathematical dilemma I would greatly appreciate any help! Here is my problem:

I have an application with a google map view that shows many thousands of pin locations. This data is retrieved over an Internet connection from our servers and displayed to the user. If the user zooms out to show a large portion of the world, then there is a large volume of geolocation data requested from the server. I need to be able to find an evenly distributed, representative subset of map pins so as to not overload the network while the user zooms in and out. Basically, I need to return x amount of map pins regardless of the zoom level, even though at zoom level 0 (zoomed fully out) there may be many many more results than at zoom level 10 (a city-wide view, for instance).

The evenly distributed portion of this problem is what I have issues with - how do I retrieve a small subset of geolocations from thousands that best represents the spread over the map.

I hope this is making sense - many thanks for any help!

If you have no further constraints then you can randomly assign numbers from 0 to 10 to each location and only show a location if the zoom level if equal or greater than the asigned number. Just make sure the frequencies correspond to how much area is covered (ie. if zoom 9 covers 4 times the area of zoom 10 then there should be 3 times as many 10's assigned as there are 1-9's.)

Of course if you consider some locations more important than others you will need to come up with an algorithm that takes this importance into account when assigning numbers.

If this method doesn't result in an even enough distribution you can divide the map into blocks this ensuring that each area has a certain number of pins with a particular assigned number.