On a circle placement problem
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.
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- scientific article; zbMATH DE number 3891419
- New clique and independent set algorithms for circle graphs
- Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
- Algorithms for Reporting and Counting Geometric Intersections
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Finding the intersection of two convex polyhedra
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- Note—On a Modified One-Center Model
- Uniform fourth order difference scheme for a singular perturbation problem
- On \(k\)-sets in arrangements of curves and surfaces
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Optimal placement of convex polygons to maximize point containment
- Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints
- Iterated nearest neighbors and finding minimal polytopes
- Near-linear time approximation schemes for geometric maximum coverage
- Optimizing squares covering a set of points
- Computing large planar regions in terrains, with an application to fracture surfaces
- A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
- Covering problems with polyellipsoids: a location analysis perspective
- New exact algorithms for planar maximum covering location by ellipses problems
- An elliptical cover problem in drone delivery network design and its solution algorithms
- Experiments with unit disk cover algorithms for covering massive pointsets
- The most points connected-covering problem with two disks
- Selecting distances in the plane
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Placing two axis-parallel squares to maximize the number of enclosed points
- In-place algorithms for computing a largest clique in geometric intersection graphs
- An algorithmic framework for solving geometric covering problems -- with applications
- Linear Time Approximation Schemes for Geometric Maximum Coverage
- Minimizing Sum of Truncated Convex Functions and Its Applications
- A lower bound on the area of a 3-coloured disk packing
- scientific article; zbMATH DE number 512834 (Why is no real title available?)
- COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET
- Computing Large Planar Regions in Terrains
- Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
- FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE
- scientific article; zbMATH DE number 2213370 (Why is no real title available?)
- Location Problems with Cutoff
- A novel approximation algorithm for max-covering circle problem
- Approximation algorithms for finding maximum containing circle and sphere
- A greedy clustering algorithm based on interval pattern concepts and the problem of optimal box positioning
- A faster algorithm for the two-center decision problem
- An improved approximation algorithm for the most points covering problem
- Dynamic maximum depth of geometric objects
- In-place algorithms for computing a largest clique in geometric intersection graphs
- Covering many or few points with unit disks
- Covering point sets with two disjoint disks or squares
- Generalized coverage: new developments in covering location models
- Enclosing weighted points with an almost-unit ball
This page was built for publication: On a circle placement problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062430)
