MINIMUM PARTITION OF RECTANGLE WITH INTERIOR POINTS

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