Next: MINIMUM SORTING BY REVERSALS Up: Miscellaneous Previous: MINIMUM SIZE ULTRAMETRIC TREE Index

### MINIMUM PARTITION OF RECTANGLE WITH INTERIOR POINTS

- 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 [191].

- Comment: Variation in which R is a rectilinear polygon is approximable within 4 [192].