3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Evil
    Aug 11, 2016 at 23:48
  • $\begingroup$ @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. $\endgroup$
    – sethmlarson
    Aug 12, 2016 at 13:12

1 Answer 1

Reset to default
2
$\begingroup$

The general problem is called Circle packing, which gets easier with equiradius circles, to get hexagonal grid and put circles on hexagon vertices and one in the center. This works on Euclidian space, so the hexagon coordinates should be converted by some kind of mapping, for example Vincenty formulae.

This method will give really neglible overlapping, but to be exact further corrections might be needed (like error calculation at intersection points to shift the centers). For small radius (like 50m) error will be very small (using the mapping to sphere). Performing grow on already available circles will give the problem of initial rotation to fit more space, so with many initial circles not fitting the grid only general method (iterative one) will give the optimum.

The deterministic optimization shows the method to treat circle packing as quadratic optimization.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.