MAXIMUM MAP LABELING

• INSTANCE: A set of n points in the plane.

• SOLUTION: 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 pairwise disjoint.

• MEASURE: The area of the squares.

  
  

• Good News: Approximable within 2 [462].

• Bad News: Non approximable within $2-\varepsilon$ for any $\varepsilon$ [168].

• Comment: 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 [137].