Optimal spanners for axis-aligned rectangles (Q706725): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Mark T. de Berg / rank | |||
Property / author | |||
Property / author: Otfried Schwarzkopf / rank | |||
Property / author | |||
Property / author: Herman J. Haverkort / rank | |||
Property / author | |||
Property / author: Mark T. de Berg / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Otfried Schwarzkopf / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Herman J. Haverkort / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2004.09.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2131984062 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A general approach to dominance in the plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4344150 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: There are planar graphs almost as good as the complete graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4945509 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new polynomial-time algorithm for linear programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applying Parallel Computation Algorithms in the Design of Serial Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph spanners / rank | |||
Normal rank |
Latest revision as of 17:55, 7 June 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