CODEWITHSUNDEEP
algorithmmathdata-structures
Alup
Alup

Reputation: 13

What are the geometric data structures that can support nearest neighbor queries in the 2d plane?

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

Upvotes: 1

Views: 70

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65437

Assuming that the weights are never negative, we can define a distance function on R2 × 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).

Upvotes: 1

Related Questions