Hi Vadim,
The question concerning fully constructed Voronoi diagram as well as Delaunay triangulation:
"find the nearest neighbor" - for a particular Voronoi cell this could be done in a constant time that depends on the number of Voronoi cell neighbors. You could also compute and store this data for all the sites within the diagram in O(N) time once the Voronoi diagram is constructed (N is total number of input geometries). "insert/erase a vertex" - You mean insertion / removal of vertices from the resulting Voronoi graph, am I right? Or insertion of a new input geometries that will require to rebuild Voronoi diagram? How long, do you think, it can take to parameterize types of coordinates,
points and point predicates?
Coordinate type is already parametrized via coordinate type traits of Voronoi builder. There is no such thing as point parametrization right now. Everything that has x() and y() method will work as a point. Predicates parametrization is already available via template parameter of the Voronoi builder. However I don't think that somebody will use this. Default Voronoi predicate kernel was designed in such a way that it operates with exact predicates at almost no cost for using them. Sounds like a magic, but that's true :-). The thing is that default static methods available in the voronoi.hpp header are not parametrized with any coordinate type traits or predicate kernels. This is made intentionally as in most cases this is not required: http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_advanced_tutorial.htm. In case you really need those you should go for the Voronoi_builder data structure that is completely configurable, (this is also covered in the advanced tutorial). The benefits of the generalized algorithm are quite significant. Many
existing libraries can use this algorithm either directly or with minimal adaptation. The parameterization of point predicates is quite important. For example, in practice, tolerance based predicates are very good alternative to multi and adaptive precision methods.
The library is already fully generalized except input point and segment types. But we are going to resolve this soon. With the right choice of predicates points using floating data types will
be supported too.
Not sure, what you mean by "predicates points". Could you explain with an example? Thanks, Andrii