The referenced article is thoughtful. However, I believe there is a "simple and elegant" solution: for geographic datasets, there are two kinds of bounding boxes. Those that do not straddle the +-180 meridian can be stored and searched as always. Those that do straddle the +-180 meridian can be stored in a semi-complementary form: namely, store the range of latitudes as usual, but instead store the range of longitudes not included within the box (and toggle a bit to indicate which form of storage is being used). Essentially no modification needs to be made to geographic indexes or search tree structures; only a slight modification is required for the search algorithms.
At any rate, here is a solution to the question itself.
I presume you anticipate the input being a sequence of bounding box descriptors ((LLx, LLy), (URx, URy)) where:
-540 <= LLx, -180 <= URx, LLx <= 180, and URx <= 180. Also -90 <= LLy <= URy <= 90.
a point at (longitude, latitude) = (x,y) is considered to lie within the BB if and only if
LLy <= y <= URy and
either LLx <= x <= URx or LLx - 360 <= x <= URx.
For output you would like parameters for the smallest bounding box containing the union of all the inputs.
Clearly the y-limits of the minimum bounding box (MBR) will be the minimum and maximum of the y-values. For the x-limits, use a line sweep to find the largest gap.
Here's a description of the algorithm. To illustrate it, suppose the input consists of four boxes,
Here is a diagram of the boxes (in red) and the MBRs (in black) of the first one, then the first two, then the first three, then all the boxes.
Notice how at the second step, boxes in the eastern and western hemispheres are surrounded by an MBR which crosses the +-180 degree meridian, making it appear as two separate boxes on this map. At the last step, that MBR has to be expanded eastwards to accommodate a small box between South America and Antarctica.
Extract all the x-coordinates of the boxes, compute them modulo 360 (to place them in the range -180..180), sort them ascending, and append the first value (incremented by 360 degrees) to the end to make them wrap around:
-149, -90, -81, -77, -69, -36, 77, 156, 211
(Notice that 211 and -149 are the same meridian.)
Think of each x-coordinate as representing the interval between the preceding coordinate (but not including that preceding value) and it. E.g., -77 represents all values from -81 through -77 but not including -81. For each of these after the first, count the number of boxes that contain that interval.
1, 0, 1, 0, 1, 0, 1, 0
For example, the first "1" means that one box covers the interval from -149 through -90. (It's the third box.)
As an optimization, you can stop the counting as soon as you find any box covering an x-interval and move on to the next x-interval. We're only trying to determine which intervals might not be covered by any boxes.
Compute the first differences of the sorted x-coordinates in (1).
59, 9, 4, 8, 33, 113, 79, 55
Match these with the coverage counts in (2). Find the largest difference for which the coverage count is 0. Here, it equals
113, the sixth element of the preceding array. This is the greatest gap in longitude left by the collection of boxes.
(Interestingly, the possibility that the maximum occurs at more than one location shows that the solution is not necessarily unique! There can be more than one MBR for a set of boxes. You can define a unique one by adding additional conditions, such as requiring that the mean distance within the MBR to the +-180 meridian be as large as possible; to resolve a tie, choose (say) the easternmost solution.)
Find the corresponding interval: here, it's from -36 through 77. This is the range of longitudes not in the MBR. Therefore, take its complement in the range from -180 to 180. Here, the complement is two disjoint intervals, one from -180 through -36 and another from 77 through 180. Alternatively, represent the complement as a single rectangle possibly straddling the +-180 degree meridian: from -283 through -36 here (or, equivalently, from 77 through 324).
Use the min and max of the y-values for the corners of the MBR.
((-283, -85), (-36, 81))