# “Practical” bounding box?

For the sake of simplicity, lets say I have a bunch of 2d points, each have X and Y. The points are distributed somewhat randomly but not completely, they will be biased to be closer to the world center (where ever that might be, completely random) and they are likely to have some kind of a shape. You can imagine that like a bunch of stars forming a galaxy around a black hole...

Now I need to process these points (each of them have a lot of calculations) and to optimize the processing, it would greatly help if I knew whether they were north of most of the other points or south, east or west and nort/south more or less than east/west. The exact specifity of the distribution is not important, right now I'm imagining 8 sectors (NNE, NEE, SEE, SSE, SSW, SWW, NWW, NNW like on the map).

2 simple but incomplete solutions to this are:

1. average the position of all the points creating the center of the collection and compare the position of each point to that. This has 2 problems. For one, 99% of the points could be in a tight circular group while one point could be waay far out somewhere. This would shift the center towards that point and in the worst case scenario, the 99% of the points would only be distributed between 2 sectors. Second problem is that the distribution doesn't have to be circular, they are just as likely to show up in the shape of a giraffe. Due to the long neck on the giraffe, the Y amplitude would be much greater than X so the processing will be incorrectly biased 50% of the time between X or Y.

2. Also compare the x and y of each point to a global min/max creating a bounding box, the bounding box can then be used to normalize x/y distribution but would suffer even more from the one lone point that could be way out there.

So in essence, I'm looking for a way to find the average position and the bounding box without being affected by the potential flyaway. The quality of those 2 pieces of data would be defined as follows: After cutting the BB into 8 sectors like a pie originating from the center point, if a point is assigned to the NNE sector for example then

1. the greatest percentage of other points must be towards its south
2. the second greatest towards its west
3. the third greatest towards its east
4. and least amount of points towards its north

Any ideas?

• 1. I'm not clear on exactly what the algorithmic task is. For each point, you want to answer "Is it north of most other points?" -- is that right? Does "north of" simply mean that the Y coordinate is larger? Does "most" simply mean "at least 50%"? Can you provide a more precise specification of the problem, so I can be sure whether the approach I'm thinking of will meet your needs? 2. What do the sectors have to do with the problem statement? Or are they there only because they're used in the candidate solution you've considered? – D.W. Jul 18 '15 at 5:33
• Welcome to Computer Science Stack Exchange. Your question is very unclear. I do not really see what the bounding box is supposed to achieve nor how it is defined. I fail to see what part of the text is the problem and what part is a half baked solution that you think might help. At first you separate the problem and your attempts at a solution. But then starting "So in essence¨ we no longer know what is the problem, or your view of the solution. – babou Jul 18 '15 at 11:25
• 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 X and for Y. NO giraffe effect, or lone star effect. Then, answering your question becomes trivial with two comparisons. What is wrong with that? But it seems so trivial that there must be a constraint you did not tell, or I did not see. What is it? – babou Jul 18 '15 at 11:37

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 > 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.

If I understand your problem statement, this can be solved efficiently using sorting. Simply sort all of the points by their Y coordinate, and for each point, remember its index in the sorted order. Now, for any given point, you can quickly identify where in the sorted list is, which immediately tells you how many points are north of it. In particular, if the node is in the last half of the list, then it's north of at least 50% of the points. So, this lets you solve your question immediately.

The running time will be $O(n \lg n)$, the time to sort all of the points.

You can do a similar computation to find the points that are east of at least 50% of the points (simply use the X coordinate instead of the Y coordinate), or the points that are north-east of at least 50% of the points (rotate the coordinate system by 45 degrees, then do the same thing), and so on. So, this lets you accomplish each of your goals.