Polynomial time algorithms for three-label point labeling

AbstractIn this paper, we present an O(n2logn) time solution for the following multi-label map labeling problem: given a set S of n distinct sites in the plane, place at each site a triple of uniform squares of maximum possible size such that all the squares are axis-parallel and a site is on the boundaries of its three labeling squares. We also study the problem under the discrete model, i.e., a site must be at the corners of its three label squares. We obtain an optimal Θ(nlogn) time algorithm for the latter problem