andre.holzner
BAN USERThere is an answer at stackoverflow, (relative path /a/17249084/288875)
The solution posted there works as follows:
* treat the array as consecutive, non-overlapping blocks of size k
* calculate 'running' minima: traverse the array from left to right.
At the start of each block, reset the variable holding the minimum seen so far,
at each position i store the minimum seen so far within this
block into an array LR[i]
* do the same thing also traversing the array in the opposite direction (from right to left),
storing the running minimum values into an array RL
Given a subarray starting at position i, the corresponding minimum is obtained as follows:
* if the subarray coincides with a block (i % k == 0 for zero based indexing), the
minimum is the last running minimum value of this block in the LR array, i.e. LR[i+k-1]
* otherwise, the subarray starting at i overlaps with two blocks: the overlap on the right
ends at i+k-1, LR[i+k-1] is then the minimum value found in the fraction of the right block
up to position i+k-1.
Similarly, the minimum of the overlap region of the block on the left starting at position i
is in RL[i].
The minimum of the requested subarray is therefore min(RL[i], LR[i+k-1])
* build a 2D range tree from the circle centers, requires O(n log n) time (see en.wikipedia.org/wiki/Range_tree )
- andre.holzner November 24, 2016* for each center (x_i, y_i), find the points within the 2D range (x_i - r_i, x_i + r_i) x (y_i - r_i, y_i + r_i), requires O(log^2 n + k) time (where k is the number of points returned which can actually be n^2 in the worst case) per point. Calculate the actual Euclidean distance between the points found in the range search and the center of circle i and check whether it is less than r_i + r_other .
if the average number of points k returned in a query does not grow with n, the total time complexity is O(n log^2 n)
(the Wikipedia article also mentions that queries can even be done in O(log n + k) time for 2D trees.