Ok, basically what I need is a data structure for storing 2D points and line segments between said points (read: edges). The order of addition of these points and lines should not affect the resulting structure too much (they will be added more or less radially around a starting point, which is pretty bad for a basic point quadtree for example) and ideally require no rebalancing in the process, it should be efficient to find the points that lie inside a specified (axis-aligned) rectangle (or a circle) and it should be efficient to find all lines that lie (completely or partially) inside a specified axis-aligned rectangle. ideally a fast method for finding the nearest neighbour of a particular point would be usefull as well, but not necessary, as selecting a rectangle around it first should speed it up enough that a trivial O(n^2) algorithm would works ok as well, and the selection will probably have to be done anyways. I read a bit in Samet's Design and Analysis of Spatial Data Structures today and it would seem a PM3-Tree might work. (Although i'd probably extend it to use buckets for the points) Have you got any other (better?) ideas? I'm mainly looking for good asymptotic behaviour as the numbers of points will definitely exceed 10000, and the number of lines will probably be a little more than twice the number of points. Memory behaviour should of course be as good as possible as well (don't want the potential performance gains to be lost again to excessive paging).

no suggestions at all?