Minimum area geometric cover for a set of line segments

3
votes

The problem I am trying to solve is:

Given a set of M points on a plane where circles can be centered and a set of N line segments which need to be covered by the circles, find the minimum area circle cover for the line segments. That is, find the radii of the circles and the centers (chosen from the M points) such that all the N line segments are covered and the total area of the circles is minimized.

Note that a line segment is covered if no part of it is OUTSIDE a circle.

Any pointers to papers or code or approximation algorithms would be great.

2
algorithmcomputational-geometry
I believe your problem is NP-hard, so you are going to have to settle for approximation algorithms. – Joseph O'Rourke
As a suggested heuristic - find the point from the possible center set that is nearest the centroid of all the line segment endpoints, and use that as the center. The radius of the circle would be the distance from that center to the farthest line segment endpoint. That should cover most cases, but I can't prove that it'll always give an optimal answer. In particular, if you have one line segment that is really far away from all the others, it may significantly skew things. – twalberg
I don't understand your solution. The possible centers of the circles are already given. I want to place circles at those centers and select their radii such that the segments are covered. – LostInTheFrequencyDomain
Ah... I think I misunderstood the question - on first reading it sounded like you wanted a single circle that was constrained to have its center in one of a limited set of positions... Having multiple circles does make this more difficult - sounds like a good match for a dynamic programming approach, though. – twalberg

2 Answers

1
votes

Edit: Just realized that the original approach (moved to the end) probably doesn't cover the case where a line segment is best covered by multiple circles very well. So I think it's better to iterate points instead of line segments, cutting the line segments down at the circle boundaries:

  1. Find the "worst" point, i.e. the point requiring the largest additional circle area for its best circle center option with the corresponding line segment at least partially in the circle. Construct / extend the corresponding circle.
  2. Remove fully covered line segments from the set and cut partially covered segments at the circle boundary.
  3. Iterate until no more line segments remain.

The main idea is to keep doing what's necessary in any case. How are overlapping circles counted? Do the areas add up, or are they merged? When going back to step one in later iterations, some kind of cost heuristics will probably be able to improve the result...

The original suggestion was:

  1. Find the "worst" line segment, i.e. the line segment requiring the largest circle for any of the circle center options and construct the corresponding circle.
  2. Remove covered line segments from the set.
  3. Iterate until no more line segments remain.
-1
votes

I just released some code to implement the suggested algorithm here:

https://github.com/usnistgov/esc-antenna-cover