Algorithm design help

Hi lainons, I'm trying to design an algorithm for finding the least amount of lines to intersect a number of circles (given by radius and center coordinates) in 2d space. I'm fairly certain the problem is NP-hard, and I'm trying to have it run in O(n^2) as an upper limit. I came up with the following algorithm: 1. generate 10 lines for each circle, with random distances from the center (but still intersecting) 2. Sort the lines by number of circles intersected 3. iterate over the sorted list, marking all intersected circles and removing a line when no new circles are intersected Any suggestions/improvements? I posted this on /g/ the other day and now I'd like some help regarding the dimensionality reduction. An anon suggested applying ISOMAP to go from (x, y, radius) to (radius, number of lines) but I'm not quite sure how I would go about this, and then how to retrieve the specific lines I'm going for... I'm a total idiot regarding stuff like this, so any help is appreciated!

I agree that it is probably NP-complete. At least it sounds like a vaguely TSP-like problem. Your algorithm will usually get an approximate answer but obviously you should not expect it to solve the problem in every case. For instance, your algorithm would be very slow in the case of having small circles that are very far apart (because you would need to randomly select a line that goes through both, which is unlikely). You might be better off only considering lines that intersect at least two circles, by choosing two points one in each circle. Better yet generate lines through each pair of circles. Even so it is not hard to find an example where this algorithm is not optimal. For instance if three points are collinear and there are two other points, the optimum solution is 2, but your algorithm might return 3 lines since it can't differentiate between a line going through 2 new points and a line going through one new point and one already-connected point. I can give a solution for the case where all circles are points (radius = 0) and no three points are collinear: make a line between two points that don't have a line through them yet, and continue until there are no more new points. I believe you can generalize this to any number of points: if n points are collinear of the set, then there is a subset whose points are "exactly n-collinear", meaning, any line through those points has exactly n points from the set. Then the above algorithm finds an optimum solution from that subset. The remaining points can form an at most exactly n-1-collinear, and you repeat the process. If you can prove that combining solutions iteratively this way works, then the problem is solved. I don't have the time to try to prove this right now (and combinatorics was never my strong suit anyway) but I couldn't think of a counterexample.

>>27045 I'm not trying to find the optimum solution every time, just a good one. Also, I think your solution for points can't be applied to a problem with circles (at least not easily transformed), since the lines don't have to pass through each center, they could even only tangentially touch the circle.

>>27050 you could try modifying it by placing points randomly within each circle and running the point-based algorithm multiple times to get the best number. When circles intersect you would want to pick points within the intersection area.

As per >>27045, your heuristic will work badly in sparse situations - where there is a lot of small circles that are far from each other. Can you give a more precise specification of the "typical" input you're hoping to get decent solutions for? Maybe by better constraining the inputs it will be easier to prove something about your solution, or come up with an even better heuristic for those cases.

>>27042 The following PDF , provides the general algorithm for Covering a Set of Points with a Minimum Number of Lines. https://stackoverflow.com/questions/49903453/greedy-algorithm-to-find-minimum-number-of-lines-that-can-intersect-all-circles is the relevant stackoverflow question. In terms of efficiency, I would approach this problem a different way. E.g. If you know the number of circles, then the same number of lines is an upper bound for the number of lines that intersect those circles. This is O(1) but has the chance to be incorrect in any case where any circles are overlapping or collinear. Then by identifying overlapping and collinear circles, you can reduce the number of lines required by each case you find. You haven't specified the length of the line, and if intersecting one point of a circle is a enough or if intersecting two points (entrance and exit) is required. In order to determine collinearity of circles, https://en.wikipedia.org/wiki/Monge%27s_theorem http://www.cut-the-knot.org/Curriculum/Geometry/MongeTheorem.shtml can be used to in order to reduce the set of points to guess from for lines that are collinear to two or more circles. Relevant references include https://cp-algorithms.com/geometry/circle-circle-intersection.html https://cp-algorithms.com/geometry/circle-line-intersection.html The second pdf is COUNTING CIRCULAR ARC INTERSECTIONS , which features an algorithm for determining intersections between circles. Another reference is https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm, which works for line segments but would have to be adapted for circles.

>>27053 The typical input would just be a set of circles with random radii >= 0 and random x- and y-coordinates. >>27059 I'm going to check out that PDF, thanks! I have already improved the heuristic by having the random lines each intersect a different circle from the set. >You haven't specified the length of the line, and if intersecting one point of a circle is a enough or if intersecting two points (entrance and exit) is required. The lines are infinite and they only have to have a non-empty intersection (the line can be a tangent or intersect at two points). Wouldn't a better upper bound for the lines be no of circles/2, since you can just have each line intersect 2 circles? >>27052 I have a feeling this would be quite inefficient, though I'd have to check to be sure. Also, I'm trying to implement this in Java, so I'm not sure if that places any constraints on the algorithm (I'd rather not implement a super complex datastructure).

>>27059 Huh, so in the Stack Overflow question they use rays instead of lines, and fix the origin. By fixing the origin you end up with a greedy algorithm that gets the optimal solution: you sweep around, you can always take the maximal (in polar coordinates) line that hasn't missed any circles yet. So one new heuristic: sample random center points and run the constrained problem. It's not clear if this generalizes to your case since you can sweep both in angle and (x, y) position.