On a circle placement problem

B. M. Chazelle, D. T. Lee

Research output: Contribution to journalArticlepeer-review

72 Scopus citations

Abstract

We consider the following circle placement problem: given a set of points pi, i=1,2, ..., n, each of weight wi, in the plane, and a fixed disk of radius r, find a location to place the disk such that the total weight of the points covered by the disk is maximized. The problem is equivalent to the so-called maximum weighted clique problem for circle intersection graphs. That is, given a set S of n circles, Di, i=1,2, ..., n, of the same radius r, each of weight wi, find a subset of S whose common intersection is nonempty and whose total weight is maximum. An O (n2) algorithm is presented for the maximum clique problem. The algorithm is better than a previously known algorithm which is based on sorting and runs in O (n2 log n) time.

Original languageEnglish (US)
Pages (from-to)1-16
Number of pages16
JournalComputing
Volume36
Issue number1-2
DOIs
StatePublished - Mar 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computational Mathematics
  • Theoretical Computer Science
  • Numerical Analysis
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'On a circle placement problem'. Together they form a unique fingerprint.

Cite this