CGAL users discussion list

[Stefan Salewski <>]

On Thu, 2013-11-07 at 09:57 +0000, Hoffmann Michael wrote:
> >> 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
> 

Thanks for your reply.

>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.

Indeed that was my initial idea -- but my hope was that there exists a
better, still simple to use heuristic algorithm.

I found some papers related to this topic, one that describes a simple,
but slow algorithm is

"L. Kou, G. Markowsky, and L. Berman, A fast algorithm for Steiner
trees, Acta Informatica 15 (1981), 141–145."

I may try that one first -- I have not many points, so that may be fast
enough.

Best regards

Stefan Salewski