# Given a list of points on a sphere find the place for another point such that most space is covered?

Suppose I knew my current location as a geographical point (Lat/Lng) and had a standard radius to search (meters). Now given a list of previously searched geographical points as the centers of circles with the same standard radius that are nearby my point but do not encompass my point what would be a good algorithm for determining where to place the center of the new geographical point such that the circle around it covers the most area not covered by other circles while also containing my current geographical point?

I've already done some thinking and I thought perhaps something to do with the average of all the points would perhaps work, but it becomes tricky because the points are on a sphere instead of on a plane.

Of course because this is the real world we must take all distances as "sphere" distances instead of straight-line distances. An algorithm which uses straight line distance but can be substituted for sphere distance is also acceptable.

I'm sure there is a name for this problem, I just could not find a name so I figured I would ask here.

• Could you give estimate on number of initial points and area to be filled? Are you looking for optimal solution or good approximation? Do you consider more general solution like iterative particle solution? Here particles are big and there are low amount of them, so it will be very efficient. – Evil Aug 11 '16 at 23:48
• @Evil A good approximation would be great, I'm planning on using the algorithm to minimize external API usage for data filling. The number of initial points will probably be between 8-10 and the radius I plan on having for each point is about 2,000 meters. All the other points will be at most 4,000 meters away from the center point, otherwise they don't matter in the calculation. – sethmlarson Aug 12 '16 at 13:12