How to find the closest point to a given query string from a set of points in O (log n) using the concept of duality?

Question

Suppose we are given a set S of n points and an arbitrary query string l. Do some preprocessing (other than duality) so that we can answer the nearest (closest) point (S) to l in O (log n) (without space limitations).

Answer 1

You say "no space restrictions", which does not require restrictions on the pre-processing time.

Consider the sorted abscissas of sites after rotation at an arbitrary angle: the site closest to the vertical line is found by dichotomy after comparisons of Lg(N) .

Now consider a continuous set of turns: you can split it into angular ranges so that the order of the sorted abscissas does not change.

So, you will find all the limiting angles, taking sites in pairs, and save the value of the angle, as well as the corresponding ordering of the rotated abscissas.

For the query, find the interval of anchor angles by first binary search (among the angles O (N²)), then the nearest site by searching for rotated abscissas (binary search among abscissas O (N)).

Done right, this will require storage of O (N³).

Given that the ordering permutations for two consecutive angles simply differ in one exchange, it is possible that O (N²) storage can be achieved using a suitable data structure.

Answer 2

The distance from the line for the point (xi,yi) is d = |yi-mxi-c|/sqrt(1+m^2) .

We need to minimize f(x,y) = (y-mx-c)^2

These are quadratic equations in (m,c) .

Satisfactory conditions: -

 F(xi,yi) <= F(x1,y1),F(x2,y2).. 

Suppose you got a solution for this, then you get the intervals (m,c) where the conditions are satisfied.

You can use the interval tree for the search interval and indicate where the string (m,c) lies.

Answer 3

You need to find a line passing through I and perpendicular to the line. Then solve a pair of equations of two lines to get the intersection. This is the closest point to I from the start line, but it is not necessarily in S Let us call the intersection I' . If your elements in S ordered by x , then you can simply do a binary search to get the closest x in S to I'.x and return the point with x .

Answer 4

You do not need to directly state this in terms of duality, but the main observation is that for two points the boundary between the lines closer to one point than the other point is a set of lines that satisfy certain inequalities for the slope and interception of the line. Therefore, if you use these inequalities, then in a sense, you consider the line as a “point” (a pair of numbers satisfying certain inequalities to find the nearest point) regardless of what you do. It seems that the only option is to do some preprocessing so that you can quickly find the closest projection of your points to an arbitrary given line (for example, by calculating a small number of projections and eliminating the rest from consideration), but this seems like a difficult make run in guaranteed O (log n ) time per query string.

Answer 5

This should work:

A preprocess with a rotating scan of the line through angles from 0 to pi, projecting all the points on this line and recording the theta angle of the scan line and the parameters for the projected points, doing this once for each moment when the two points coincide, i.e. “intersect” each other. By “parameters” I mean the choice of any fixed origin A and the record (p - A) of the point [cos theta, sin theta] for all p. There will be O (n ^ 2) of these line records scans, so they can be searched by angle in O (log n). For the query string Q, use binary search to find two recorded scan lines that bracket Q perpendicular to the angle. Recorded projections have the same point order as the point order, perpendicular to Q. Now find the parameter for the point R, which is the projection of Q onto its own first through the perpendicular A. Use another binary search in the scanning lines bracketing to find the point closest to B. This is the closest point Q.