Alex Rivera | Logout

Data structure for storing thousands of vectors

Asked 2009-12-17T10:10:43.110
13

I have upto 10,000 randomly positioned points in a space and i need to be able to tell which the cursor is closest to at any given time. To add some context, the points are in the form of a vector drawing, so they can be constantly and quickly added and removed by the user and also potentially be unbalanced across the canvas space..

I am therefore trying to find the most efficient data structure for storing and querying these points. I would like to keep this question language agnostic if possible.

algorithm language-agnostic data-structures
Edit
Report

1 Answer

6

I would like to suggest creating a Voronoi Diagram and a Trapezoidal Map (Basically the same answer as I gave to this question). The Voronoi Diagram will partition the space in polygons. Every point will have a polygon describing all points that are closest to it. Now when you get a query of a point, you need to find in which polygon it lies. This problem is called Point Location and can be solved by constructing a Trapezoidal Map.

The Voronoi Diagram can be created using Fortune's algorithm which takes O(n log n) computational steps and costs O(n) space. This website shows you how to make a trapezoidal map and how to query it. You can also find some bounds there:

  • Expected creation time: O(n log n)
  • Expected space complexity: O(n) But
  • most importantly, expected query time: O(log n).
    (This is (theoretically) better than O(√n) of the kD-tree.)
  • Updating will be linear (O(n)) I think.

My source(other than the links above) is: answered 2009-12-17T11:39:52.023

Your Answer