Calculating the bounding box for geographic coordinates

Question

Given a list of coordinates, how do I calculate the minimum bounding rectangle (MBR), avoiding the global gotchas described in the Unlocking the Mysteries of the Bounding Box?

Google Maps API method fitBounds() seems to be handling the gotchas well.

Edit:

Using an example from the article above, let's say I have to calculate a bounding box for two locations in the imaginary country of Boxtopia: point A(170, 40) and point B(-170, 50). If construct my bounding box using xmin, ymin as the southwest corner and xmax, ymax as the northwest corner, I'll get (-170, 40) and (170, 50) respectively, a box which would span 340 degrees instead of minimum 20 degrees.

Answer 1

For the 1D problem, you are looking for the largest empty interval on a 'circle'. Sorting the data, and then looking for the largest gap will provide the answer in O(N.log(N)).

Answer 2

One easy solution is to sort the x coordinates and incrementally add add 360 to the lowest values and see if it results in a smaller bound.