[bimfphbt] Steiner trees

Steiner trees are visually appealing.  although they are theoretically NP-complete, I suspect that, like traveling salesman, many instances with small numbers of points can be solved or approximated well enough to be visual appealing.  the Euclidean Steiner tree problem can be quickly approximately solved with an analog computer: soap films.

set up a collection of moving points, perhaps particles colliding with walls, and compute the Euclidean Steiner tree for every frame.

the rectilinear Steiner tree problem requires all segments be horizontal or vertical.  this can be generalized, specifying a different set of angles (slopes) that all segments must be.  aesthetically pleasing might be segments parallel to the edges of a regular hexagon.  also consider continuously uniformly turning the set of permitted angles for a given set of fixed points.

consider the Steiner tree problem on graphs on a pixel grid.  nodes are pixels and edges are adjacency between neighboring pixels.  select a subset of pixels that need to be connected.  a typical display has millions of pixels, so this is no longer a small Steiner tree problem.  does the Steiner tree problem on graphs become easier if the underlying graph is very regular, a lattice?

there are typically many shortest paths between two pixels: binomial function, Manhattan distance.  does this issue of multiple solutions compound when connecting more than two pixels?  if so, how can families of solutions be depicted?

also consider hexagonal pixels.  also consider pixel grids with some pixels missing.  this was inspired by the road network in the game Civilization 4: you can't build a road through water or mountain tiles.