TY - JOUR

T1 - Polynomial time algorithms for three-label point labeling

AU - Duncan, Rob

AU - Qian, Jianbo

AU - Vigneron, Antoine

AU - Zhu, Binhai

N1 - Funding Information:
This research is supported by NSF of China, Hong Kong RGC CERG grants City U1103/99E, HKUST6088/99E and DAG 00/01.EG27. Part of this research was done when the second and the fourth author were with City University of Hong Kong. ∗Corresponding author. E-mail addresses: [email protected] (Antoine Vigneron), [email protected] (B. Zhu).

PY - 2003

Y1 - 2003

N2 - In 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 Θ(n log n) time algorithm for the latter problem.

AB - In 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 Θ(n log n) time algorithm for the latter problem.

KW - Algorithms

KW - Map labeling

KW - NP-hardness

UR - http://www.scopus.com/inward/record.url?scp=0037268208&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(02)00433-4

DO - 10.1016/S0304-3975(02)00433-4

M3 - Conference article

AN - SCOPUS:0037268208

SN - 0304-3975

VL - 296

SP - 75

EP - 87

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

T2 - Computing and Combinatorics

Y2 - 20 August 2001 through 23 August 2001

ER -