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 -