CGAL users discussion list

[Bernd Gaertner <>]

Andy Hirsh wrote:
> for an optimization algorithm I would like to know if there is a way
> to evaluate the minimum path along some (eg 1000) vectors using
> CGAL...  all vectors need to be traversed only once,  I can
> change the directions of vectors and I can also add some "jump
> vectors" if needed...

It seems that you are talking about a variant of the traveling 
salesperson problem (TSP) which is notoriously difficult even for small 
inputs, and in two dimensions. As a CGAL editor, I'm flattered that you 
consider CGAL a possible source of solutions, but I'm afraid that this 
is beyond the scope of CGAL. I throught a little bit about whether the 
flexibility of changing vector orientations makes the problem easy in 
some miraculous way, but I could not think of anything.

There are reasonable heuristics for TSP, some of them even with 
approximation guarantees (see for example 
http://en.wikipedia.org/wiki/Traveling_salesman_problem); you might want 
to try some of them, and then CGAL might come handy to do certain basic 
computations.

Best,
Bernd.