Next: MINIMUM SORTING BY REVERSALS
Up: Miscellaneous
Previous: MINIMUM SIZE ULTRAMETRIC TREE
Index
- INSTANCE:
Rectangle R and finite set P of points located inside R.
- SOLUTION:
A set of line segments that partition R into rectangles such that
every point in P is on the boundary of some rectangle.
- MEASURE:
The total length of the introduced line segments.
- Good News:
Approximable within 1.75 [203].
- Comment:
Variation in which R is a rectilinear polygon is approximable within 4
[204].
Viggo Kann
2000-03-20