Is there a way of picking a minimal set of disks that's still covering the same line subsegments as all the disks together? Any help or references highly appreciated. Below is just an illustrative picture, because I actually have 10.000 disks.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ By "covering a line segment" do you actually mean "intersecting a line segment," i.e., only partially covering in general? The term "cover" usually means "completely cover." But in your example, none of the segments are fully covered. $\endgroup$– Joseph O'RourkeCommented Sep 4, 2019 at 0:17
-
$\begingroup$ Given one of the above blue lines, by a segment I mean any part (interval) of it. The question is actually only about the segments which are inside at least one of the circles. In other words, anything blue which is not inside a circle can be ignored in this question. In particular, to answer your question @JosephO'Rourke, I do not mean intersections. Yes, cover means 'complete cover'. $\endgroup$– Ajdin HalilovicCommented Sep 4, 2019 at 14:37
-
1$\begingroup$ I see. Incidentally, those blue "lines" are actually what are normally called "segments," and what you are discussing are subsegments of those segments covered by one or more disks. $\endgroup$– Joseph O'RourkeCommented Sep 4, 2019 at 14:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
This will be a high-level suggestion, and definitely not optimal.
First, execute a sweepline algorithm to detect all the points of intersections between segments and circles. Then for each segment, run along it and discard portions not covered by any disk. Now you are left with subsegments, each of which is covered by one or more disks.
For each disk, record which subsegments it covers. Discard a disk if it covers no subsegment. Now the suboptimal part: if all of the subsegments a particular disk covers are covered by more than one disk, discard that disk, and repeat. This is a mindless discarding and would not in general achieve the minimal cover.
If you really need the minimal cover, you'll have to proceed analogously to this paper, as the problem is almost certainly NP-hard:
Alt, Helmut, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph SB Mitchell, and Kim Whittlesey. "Minimum-cost coverage of point sets by disks." In Proceedings of the 22nd annual symposium on Computational geometry, pp. 449-458. ACM, 2006. arXiv preprint cs/0604008.
answered Sep 4, 2019 at 15:07
-
1$\begingroup$ Thank you very much for the reference! It probably addresses exactly the question I have, but in order to be sure I first need to read the paper :) $\endgroup$ Commented Sep 5, 2019 at 9:51
$\begingroup$
$\endgroup$
You can formulate this as a set covering problem. For each circle $j$, define a binary variable $x_j$ that indicates whether circle $j$ is selected. Let $C_i$ be the set of circles that intersect line segment $i$. The problem is to minimize $\sum\limits_j x_j$ subject to $\sum\limits_{j \in C_i} x_j \ge 1$ for each line segment $i$ with $|C_i|>0$.
