Polynomial time algorithms for three-label point labeling

Rob Duncan; Jianbo Qian; Antoine Vigneron; Binhai Zhu

doi:10.1016/S0304-3975(02)00433-4

Polynomial time algorithms for three-label point labeling

Rob Duncan, Jianbo Qian, Antoine Vigneron, Binhai Zhu^*

^*Corresponding author for this work

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Contribution to journal › Conference article › peer-review

7 Scopus citations

Abstract

In this paper, we present an O(n²logn) 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.

Original language	English (US)
Pages (from-to)	75-87
Number of pages	13
Journal	Theoretical Computer Science
Volume	296
Issue number	1
DOIs	https://doi.org/10.1016/S0304-3975(02)00433-4
State	Published - Jan 1 2003
Event	Computing and Combinatorics - Guilin, China Duration: Aug 20 2001 → Aug 23 2001

Keywords

Algorithms
Map labeling
NP-hardness

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/S0304-3975(02)00433-4

Cite this

@article{664c718719eb49699983f3efcd15df59,

title = "Polynomial time algorithms for three-label point labeling",

abstract = "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.",

keywords = "Algorithms, Map labeling, NP-hardness",

author = "Rob Duncan and Jianbo Qian and Antoine Vigneron and Binhai Zhu",

year = "2003",

month = jan,

day = "1",

doi = "10.1016/S0304-3975(02)00433-4",

language = "English (US)",

volume = "296",

pages = "75--87",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

note = "Computing and Combinatorics ; Conference date: 20-08-2001 Through 23-08-2001",

}

TY - JOUR

T1 - Polynomial time algorithms for three-label point labeling

AU - Duncan, Rob

AU - Qian, Jianbo

AU - Vigneron, Antoine

AU - Zhu, Binhai

PY - 2003/1/1

Y1 - 2003/1/1

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 -

Polynomial time algorithms for three-label point labeling

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this