"Practical" bounding box?
For all I can understand of your problem, you want to find a median
point serving as center such that half your points are north, half
south, half west, half east.

This is not a center of gravity, since distances do not seem to
matter. This can be done by computing separately the median for all $X$s and
for all $Y$s. There are no giraffe effect, or lone star effect, or other.

Computing this median $X_M$ and $Y_M$ for all $X$s and $Y$s can be done in linear time $O(n)$
where $n$ is the number of points, as indicated in wikipedia and StackOverflow.

Then for any point $(X,Y)$ you can know  whether it has more points
south (low ordinates) by checking whether $Y &gt; Y_M$, and conversely
for more points north.

Similarly by comparing $X$ to $X_M$ you can tell whether ther are more
points east or west of point $(X,Y)$

You can get similar results along any direction.