A Note on three-label point labeling
Antoine Vigneron · 2001
Let P be a set of n points in the plane. We want to find a set S(P; l ) of axis--parallel squares with edge length l such that each point of P is associated with three squares, each point of P lies on the boundary of its three associated squares, no two squares of S(P; l ) intersect, and l is maximized. We show how to solve this problem in O(n 2 log n) time. 1