Optimal spanners for axis-aligned rectangles (Q706725)

The authors propose an approach to the problem of finding the connection segments that minimize the dilatation in a bridge graph, i.e. the graph which describes which pairs of rectangles from the given non-intersection rectangles are to be connected. It is proved that the graph contains cycles, then the problem cannot be solved in polynomial time, but if the graph is a path or a tree, then the problem has polynomial complexity. It is also proved that in the case of a set of rectangles sorted vertically along a path, an estimate of the problem solution can be found in linear time.