Polynomial time algorithms for three-label point labeling

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

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)75-87
Number of pages13
JournalTheoretical Computer Science
Issue number1
StatePublished - 2003
Externally publishedYes
EventComputing and Combinatorics - Guilin, China
Duration: Aug 20 2001Aug 23 2001

Bibliographical note

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: antoine@cs.ust.hk (Antoine Vigneron), bhz@cs.montana.edu (B. Zhu).


  • Algorithms
  • Map labeling
  • NP-hardness

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Polynomial time algorithms for three-label point labeling'. Together they form a unique fingerprint.

Cite this