How to find a nearest point to a given query line from a set of points in O(log n) time with out using duality concept?

Question

Assume that we have been given a set S of n points and an arbitrary query line l. Do some preprocessing (other than duality) so that we can answer the nearest (closest) point (of S) to l in O(log n) time (no restriction on space).

Answer 1

You say "no restriction on space", which implies no restriction on preprocessing time.

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

Now consider the continuous set of rotations: you can partition it in angle ranges such that the order of the sorted abscissas does not change.

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

For a query, find the enclosing angle interval by a first binary search (among O(N²) angles), then the closest site by a search on the rotated abscissas (binary search among O(N) abscissas).

Done the straightforward way, this will require O(N³) storage.

Given that the ordering permutations for two consecutive angles just differ by a single swap, it is not unthinkable that O(N²) storage can be achieved by a suitable data structure.