On a circle placement problem (Q1062430): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms for Reporting and Counting Geometric Intersections / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Note—On a Modified One-Center Model / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finding the intersection of two convex polyhedra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3694703 / rank | |||
Normal rank |
Latest revision as of 18:38, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a circle placement problem |
scientific article |
Statements
On a circle placement problem (English)
0 references
1986
0 references
We consider the following circle placement problem: given a set of points \(p_ i\), \(i=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=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^ 2\log n)\) time.
0 references
circle placement problem
0 references
maximum weighted clique problem
0 references
0 references