7

What kind of algorithm can I use to search for an optimal (minimum area) covering of a limited region of the XY plane with n discs ( xj, yj, rj ) ?

I've found many investigations on fixed radius discs, but nothing about variable radius.

n is fixed but the discs can be placed freely (they're not in assigned positions and their centers are not required to be inside the region). The region is in general non-connected and non-simply connected (can be composed by multiple parts and can have holes). In my specific case is defined by multiple closed polygons (using odd-even filling rule).

To recap:

Input:

  • a limited area of the XY plane (e.g. described as a collection of closed polygons with odd-even filling rule)

  • an integer number n > 0

Output:

  • a list of n discs described by center x[i], y[i] and radius r[i] so that every point of the area is contained in at least one disc

Minimizing:

  • the area of the plane covered by the union of the discs

Example

Example of solution

In this example the input was the "A" shape. Ten points were placed manually and minimal circles covering the intersection of the area with the Voronoi cells were computed.

I'm currently investigating the approach based on just looking for the centers x[i], y[i] and computing the radiuses r[i] with this algorithm (search space is reduced by ℝn and always produces an acceptable solution).

Community
  • 1
  • 1
6502
  • 112,025
  • 15
  • 165
  • 265
  • 1
    An evolutionary algorithm should give a reasonable heuristic approach. Perhaps some quadratic programming approach (with quadratic constraints from the equations of a circle) could yield an optimal solution. – John Coleman Mar 19 '19 at 13:26
  • Are you given the positions and sizes of the discs, and need to choose a subset of them that covers every point in the region and has the minimum sum of included disc areas? – j_random_hacker Mar 19 '19 at 13:53
  • @j_random_hacker: the position of the center and radius is free... i've to optimize the area of the union of the circles. There is no prescribed set of discs (or even radiuses) to choose from. – 6502 Mar 19 '19 at 14:00
  • And the goal is to cover every point in the region with at least one circle? – j_random_hacker Mar 19 '19 at 14:04
  • @j_random_hacker: yes exactly: nothing should be left out (all points in the region should be covered by at least a disc), but i want to minimize the area **outside** the region that is covered by the discs (i.e. I want the total area covered by the discs to be minimal, however this area clearly cannot be smaller than the area of the region). – 6502 Mar 19 '19 at 14:30
  • If you do not give a smallest possible radius, I'd assume that the solution will contain infinite discs with radius approaching zero. – mikuszefski Mar 19 '19 at 14:47
  • 2
    @mikuszefski `n` seems to be a parameter of the problem, which would rule out solutions with arbitrarily small radii. – John Coleman Mar 19 '19 at 14:53
  • I see. I'm afraid I don't see a tidy solution... Long, narrow segments of the target region are going to hurt, and it seems difficult to avoid creating "remaining scraps" of this shape as you incrementally add discs. – j_random_hacker Mar 19 '19 at 14:59
  • @mikuszefski I've added a clarification that `n` is fixed: parameters to the problems are `n` and the area to be covered, result is a list of `n` triplets `(x, y, r)` covering all the area but the least possible amount of non-area. – 6502 Mar 19 '19 at 15:19
  • Imho, I think your question would raise more interest, and possibly more answers, on the [computer science stack exchange](https://cs.stackexchange.com/). – m.raynal Mar 19 '19 at 15:19
  • I would suggest replacing circles with "fuzzy disks". With a boundary region where you go from penalized for outside to rewarded for inside. Then use simulated annealing. As you anneal, the reward for inside goes up, and the fuzzy region gets narrower and narrower. – btilly Mar 19 '19 at 19:07
  • @6502 If you need just close to optimal then how about physics simulation where you place the discs randomly "far" away and they attract so they stick together ... try more runs or shakes and remember the best solution, you can also add some heuristics like set the biggest disc to fixed position with biggest "mass"... for more info see related: [How to implement a constraint solver for 2-D geometry?](https://stackoverflow.com/a/40827518/2521214) you can combine this with some path towards center [Path generation for non-intersecting disc](https://stackoverflow.com/a/30639417/2521214) – Spektre Mar 20 '19 at 09:47
  • The Voronoi decomposition is a great idea. I expect that Voronoi cells with extreme aspect ratios would be the ones whose covering circles produce the most waste, so perhaps you could modify your approach by placing fewer than n points initially, then measuring the aspect ratios of the resulting cells, and distributing the remaining points inside those cells with the highest or lowest aspect ratio. Alternatively you could hill-climb by moving each of the points a small amount in each direction and recomputing, then picking the single point movement that decreases area the most. – j_random_hacker Mar 21 '19 at 09:47

1 Answers1

0

This is a really cool problem! I'm glad I stumbled on this one. I fully realize that this is over a year old, so you probably don't care about it anymore, but I'll answer it either way because I like riddles and this was a fun one (assuming my solution even works!).

What I would do seems similar to the Voronoi diagram suggestion:

  1. Start with a hierarchical clustering solution to the problem. It won't have minimal area, but it will cover everything with N disks.

    a. Note: I wouldn't use K-means because K-Means tends to get caught in local minima quite easily.

  2. You could probably then use gradient descent to move the centers of the disks (with the loss being the total area of each disk -- computed as the miximal distance to the points within this "cluster") to get you a more optimal solution.

I think some caveats here would be if you have a few lone points, they might lead to some undesirable solutions.

There's obviously no proof that this would work. What do you think? Also, what did you end up using?

Aaron
  • 801
  • 6
  • 13