Skip to main content
added 27 characters in body
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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 twenty-second22nd annual symposium on Computational geometry, pp. 449-458. ACM, 2006. arXiv preprint cs/0604008arXiv preprint cs/0604008.

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 twenty-second annual symposium on Computational geometry, pp. 449-458. ACM, 2006. arXiv preprint cs/0604008.

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.

Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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 twenty-second annual symposium on Computational geometry, pp. 449-458. ACM, 2006. arXiv preprint cs/0604008.