Next: MINIMUM PHYLOGENETIC TREE DISTANCE
Previous: SHORTEST PATH MOTION IN
A set of n points in the plane.
A collection of n axis-aligned equal-sized squares (labels) such that
(a) every point is the corner of exactly one square, and (b) all squares are
The area of the squares.
- Good News:
Approximable within 2 .
- Bad News:
Non approximable within
The generalized problem, where equal-sized rectangles or ellipses are allowed
as labels, and where the labels may have any orientation and may have any
point on the boundary at the point in the plane, is in APX. The generalized
problem is approximable within 14 when the labels are squares and within
15 when the labels are circles .