I was wondering if there exist a data structure that can support the following operations(ideally in log(n)

time where n is the number of points):

1. Nearest neighbor queries where the nearest neighbor to a point is defined as the function that takes the point and returns the point that gives the minimum sum of its weight plus its distance from the queried point.
2. Insertion of a new point into the data structure
3. Bulk Updating of the weight of all current points in the structure by a given number

CodePudding user response：

Assuming that the weights are never negative, we can define a distance function on R² × R (points × weights) as d((p, w), (p′, w′)) = d(p, p′) |w − w′|. Weird metric, but it plugs right into the cover tree nearest neighbors algorithm. Then we query a point p by first embedding it as (p, v) where v = 0.

To add a constant c to all of the weights, we adjust the “vantage point” v by v ← v − c. A new point p added to the structure with weight w embeds as (p, w − v).