4
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

This is equivalent to finding all the points in a query half-plane, which has a cute, non-obvious solution in terms of convex layers, using fractional cascading to speed up moving from layer to layer.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user150717
    Commented Jun 29, 2022 at 13:03
  • 1
    $\begingroup$ @DannyBlozrov: More or less, though if any of the outermost convex layer's points are inside the half-plane, you can quickly find one (a "deepest" one in fact) by binary-searching for an boundary line segment with slope equal to the half-plane's slope (it seems to me that this requires a "directional" notion of slope to avoid finding a "furthest-away" point). More details here. $\endgroup$
    – j_random_hacker
    Commented Jun 30, 2022 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.