ON A CIRCLE PLACEMENT PROBLEM.

B. M. Chazelle, D. T. Lee

Research output: Contribution to conferencePaper

1 Scopus citations

Abstract

We consider the following circle placement problem: given a set of points p//i, i equals 1, 2, . . . ,n, each of weight w//i, 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, D//i, i equals 1, 2, . . . , n, of the same radius r, each of weight w//i, find a subset of S whose common intersection is nonempty and whose total weight is maximum. An O(n**2) 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(n**2logn) time.

Original languageEnglish (US)
Pages333-337
Number of pages5
StatePublished - Dec 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'ON A CIRCLE PLACEMENT PROBLEM.'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B. M., & Lee, D. T. (1984). ON A CIRCLE PLACEMENT PROBLEM.. 333-337.