CGAL users discussion list

[Rupert Mazzucco <>]

Bonjour la liste,

I'm thinking about using a cgal seach structure (either 2D nearest 
neigbor/range, or dD spatial searching) for my simulation.  I have looked at 
the manual and tried some examples, but am still not sure if cgal is 
appropriate for my needs.  I would appreciate some input from someone who has 
some actual experience with nearest neighbor searching.

So, what I need to do is the following:

- I'll have to store about 100-10000 points (cartesian coordinates, normal 
doubles or floats, standard euclidean metric).  I need 2D points now, but 
could at some point in the future make use of 3-5 dimensions.  That's not 
absolutely necessary, though.
- I need to store information along with the coordinates, or at least an 
integer index.
- I need to remove and reinsert nodes frequently.  Typically, I'd remove and 
insert a handful of random nodes and then pick one random point and do a 
neighbor search on it.
- When performing a search, I'll need to find about k = 1-100 neighbors.  
Approximate search would be fine, I could specify either k directly or a 
(circular) range.  I'd use incremental search only rarely and could avoid it 
altogether at the expense of giving a maybe overly generous range or number k.

I don't see (yet?) how to associate an index with the Point_2<> thingy, and 
the k-d tree doesn't seem to support node removal.  Is that correct or did I 
overlook something?  How is the relative performance of these to structures 
in the 2D case?  Is there a point in using it at all, when I need to update 
my nodes frequently as described?

Thank you,
Rupert
-- 
Rupert Mazzucco         
<>
Research Scholar, Evolution and Ecology Program
IIASA - Institute for Applied Systems Analysis
Schlossplatz 1, 2361 Laxenburg, Austria
Phone: +43 2236 807 522   Fax: +43 2236 713 13