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

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.

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

Keywords

  • Algorithms
  • Map labeling
  • NP-hardness

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this