Find minimum number of points which intersect overlapping arcs Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time.
I'm having some trouble proving that my algorithm works. I'm getting caught up with arc intervals that span $0,2\pi$.
For example I have the intervals (in degrees): [45,90],[315,50],[300,25],[310,350] - when I do a sweep I find that the first degree with the least intersects (2) - is 25 - committing to this yields needing 3 points {25,45,310}, whereas the optimal solution is 2 points {~45,~350}. I'm thinking I can maybe just exclude that angle of the least intersects - but I'm not sure how to prove I won't run into a similar problem with a different set of arcs?
So far I have:
# place Intervals in a minHeap based on &quot;starting&quot; radian/degree O(n)
# i = sweep intervals to find first radian/degree with least intersects O(n)
p = float(+inf)
P = {}
while minHeap is not None:
  I = minHeap.deleteMin()
  if I.start&gt;I.end: 
    I.end += 360   # trying to normalize
  end if

  if I.start &lt; i: 
    minHeap.insert(new interval with I.start + 360 and I.end +360) #too early to evaluate
  else:
    if I.last &lt;= p: 
      p = I.last #looking for the counterclockwise radian/degree which covers most arcs
    end if
    
    if I.first &gt; p:
      #found an interval out of reach - updating trackers
      p = p % 360 #normalizing
      P[p] = true #will eventually return P
      p = I.last  #updating to the new most counterclockwise rad/degree
    end if
  end if
end while
return P
A little abstraction would help both reasoning about and solving the problem efficiently, I think.
For every point $x$ on the circle, there is some set $S_x$ of pairwise overlapping arcs that intersect this point. Now, if there is some other point $y$ such that $S_x \subseteq S_y$, you can always use $y$ instead of $x$ in a solution to your problem. We can therefore focus on a set of representative points $x_1,\ldots,x_m$ such that each set $S_{x_1},\ldots,S_{x_m}$ is maximal. There are at most $n$ such points (the proof of which I will leave as an excercise) and you should be well able to find this set in $O(n^2)$ time.
Now, if the arcs don't wrap all around the circle, i.e. there is some point on the circle that doesn't touch any arcs, then you can look at the arcs as intervals on a straight line. Given the right infrastructure (you should sort the arcs both by starting and ending angle, again easily doable in $O(n^2)$ time) you can solve this problem greedily in $O(n)$ time (cf. this post).
Finally, to solve the problem, you do as follows: For each $1\leq i\leq m$, you ask the following question: &quot;If i use $x_i$, how many other points must I use in order to cover the arcs that are not in $S_{x_i}$?&quot; These arcs naturally do not wrap around the circle. You can therefore calculate this in linear time, and return the minimum set of points over all tries. Since $m\leq n$, this will only take $n^2$ time in total.