Optimal spanners for axis-aligned rectangles (Q706725): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Mark T. de Berg / rank | |||
Property / author | |||
Property / author: Otfried Schwarzkopf / rank | |||
Property / author | |||
Property / author: Herman J. Haverkort / rank | |||
Revision as of 04:27, 21 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal spanners for axis-aligned rectangles |
scientific article |
Statements
Optimal spanners for axis-aligned rectangles (English)
0 references
9 February 2005
0 references
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.
0 references
optimal spanners
0 references
rectangles
0 references
minimized dilatation
0 references
Geometric spanners
0 references
Dilation optimization
0 references
Isothetic rectangles
0 references
Manhattan distance
0 references
bridge graph
0 references
polynomial complexity
0 references