On Wed, 2 Jun 2010, Eric Fowler wrote:

I have a bit of a problem here, and would like some input.  I am working on an optimization algorithm that makes much use of shortest-paths and near-neighbor concepts. 

To get a reasonable near-neighbor search on points on the Euclidean plane, I have implemented (mostly) a Delaunay tree as a Boost graph. The points on the graph represent points in space, and are unique. I make use of angles and cosines and such to find neighbors and so on. The Delaunay graph is a basis for the optimization and shortest-paths stuff, which encompasses concepts other than just points-in-space, like type-of-point and so on. The basic idea is that when I am traversing my graph looking for optimal paths and such, I use the Delaunay graph to find near neighbors. 

How dynamic is your point set? How large?

Now, here is the problem: my graph really needs for vertices to share points in space. Each vertex has a location and other properties, so there needs to be several vertices at one point. To have a Delaunay graph with coincident points is not really meaningful; the geometry gets really weird (e.g. what is the angle between three coincident points?). 

Do you logically have several points at one location (just merged into one for Delauney to work) with each one as a vertex, or actually have several vertices mapped to the same point?

So I had figured I could build the Delaunay graph, and put a thin layer on it that handled reference counts for points in space, and stored vertices with all their attendant extra information. So I would make a class that had a map<> of points-in-space and their refcounts, and as I added or deleted points I would bump the counter. As far as the Dr. Delaunay knew, all points would be unique; every coincident point would share it's neighbors with it's brothers. 

Problem is, how to do a (for instance) breadth-first search over this graph, in which the graph algorithm needs to "see" each point individually? 

My thinking right now is that I can have my structure as described and build a custom iterator, then pass the iterator to the various search algorithms and visitors and what not. The iterator would have the intelligence to sort out the non-unique points.

I think the answer depends on your data size and how dynamic it is. For small data, the naive solution of just keeping the graph explicitly and putting in whatever edges between vertices are suggested by your triangulation is probably the easiest approach (and the easiest to ensure the correctness of). If you have very large data sets you might need a graph that uses less storage and we can discuss that in more detail.

So the simple question is: am I on the right track? Is this kind of thing feasible or supported by the library? If it is, how do I specify my iterator to the various algorithms?

You would need to build your own graph type, with your iterators as its vertex, edge, out edge, ... iterators. But let's make sure a simpler solution isn't feasible before we discuss that level of effort.

Alternatively, does anyone know if it is possible to build a Delaunay graph with coincident points that has geometric meaning, i.e. preserves the properties we associate with Delaunay graphs? This is really a math question ... 

This is not my area of expertise, so I can't answer this question. -- Jeremiah Willcock