CGAL users discussion list

["Hoffmann Michael" <>]

>> I am looking for a way of finding an Euclidean minimum Steiner tree for
>> a set of points in 2d. An approximation would be OK. I found some
>> theoretical papers about this problem -- may there exist some support
>> for this task in CGAL, or can you recommend a not too complicated paper
>> describing an algorithm?
> 
> If I remember right,  you can compute a Delaunay triangulation
> and then compute the MST from that. For the latter you can use
> the BGL.

That's the EMST. In the Steiner variant you may add additional 
points/vertices, which is a completely different game.
There is a PTAS for the geometric version, and there are approximation 
algorithms for the corresponding graph problem.

One thing you could easily try is: start from the EMST as a base, then add 
one or several points, compute the EMST again and compare.
As far as how to choose the additional points, there are various options. 
Maybe Fermat points of three points are a good option? Maybe try to choose an 
optimal point from a grid?
Obviously, this is a heuristic, and the only guarantee might be that it's not 
worse than the EMST. :)

Best,
Michael