CGAL users discussion list

[Manuel Holtgrewe <>]

Hi list,

I try to find an implementation of exact nearest neighbor search using
kd-trees. My questions aim at whether it is easy to change the
existing Orthogonal_k_neighbor_search class so the queries are exact.
Building the kd tree should be "exact" even for
Exact_predicates_inexact_construction_kernel since comparison is only
performed on the coordinates but not on the euclidean distance etc.


I have a question regarding the kd-trees in CGAL: In which sense are
the CGAL kd-trees approximate? I have read the source code and there
seem to be at least two points where they are approximate:

First, you can give a double value Eps that tweaks the slack in
comparison when doing the "unrolling" of the recursion.

Second, after finding k approximate nearest neighbours, the search
stops. This means that for k=1 only the downward part of the search is
execute in the kd-tree.

Is this correct so far?

Now in which part are exact arithmetics used? The
Orthogonal_k_neighbor_search class template is parametrized with the
used kernel through the SearchTraits. Naïvely, I would expect that
passing a Exact_predicates_inexact_construction_kernel through the
SearchTraits, except for the two points above, the query should be
"exact".

For computing the distance, Euclidean_distance<SearchTraits> is used.
Are the comparisons exact when using the
Exact_predicates_inexact_construction_kernel?

Also, there are some arithmetic operations like addition and
subtraction used in the source code of the
Orthogonal_k_neighbor_search. Would they harm exactness.

Bests,
-- Manuel