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.

$\endgroup$
0

1 Answer 1

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

$\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$ Jun 29 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$ Jun 30 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.