# n points in 2d plane and a method(a,b) that returns all points closer to 0 than (a,b)

Given n points in a 2d plane I.E $$(x_1,y_1),(x_2,y_2)\dots (x_n,y_n)$$.

Create a data structure that holds the points and a method closer$$(a,b)$$ that returns all the points in the data structure that are closer to $$(0,0)$$ than to $$(a,b)$$.

The preprocessing and creation of the data structure have no complexity limit but the closer$$(a,b)$$ has a time complexity of $$\mathcal{O}(\log(n)+k)$$ where n is the number of points and k is the amount of points closer to $$(0,0)$$ .

I'm quite certain it involves self balancing binary search trees, but not sure how to implement it. If $$(a,b)$$ is given during preprocessing then we can just make an array and sort it with $$d=(x_i-0)^2+(y_i-0)^2-((x_i-a)^2+(y_i-b)^2)$$. That would give us a search in $$\log(n)$$ on the first element in the array that is bigger than $$0$$ and then we can just run a for loop j times.

If (a,b) is not given during preprocessing then I don't know how to approach this, I tried switching to polar coordinates or trying to find the mathematical Locus but It didn't seem to get me anywhere.

• Appreciate the reference. So basically for my purposes the cut in the middle $(a,b)$ and $(0,0)$ creates a half plane. If I take a shell of convex shapes, recursively(for example take the most outer points possible and make a convex shell, then go deeper recursively). For the biggest convex shell we check a few points and going along the slope, once we reach a point that is outside, we are pointed to an inner shell and we check them the same way. Once we reach a shell that doesn't touch the cut, we are done? Apologies for bad terminology, non native English speaker. Jun 29, 2022 at 13:03