1
$\begingroup$

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 "starting" 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>I.end: 
    I.end += 360   # trying to normalize
  end if

  if I.start < i: 
    minHeap.insert(new interval with I.start + 360 and I.end +360) #too early to evaluate
  else:
    if I.last <= p: 
      p = I.last #looking for the counterclockwise radian/degree which covers most arcs
    end if
    
    if I.first > 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
$\endgroup$
5
  • 1
    $\begingroup$ There must be some constraints that haven't been stated. Otherwise, the more points I add, the more arcs I can overlap, and I don't see any limit on the points. Can you proofread your question and make sure you have accurately stated the full task? Where did you encounter this? Can you credit the original source? $\endgroup$ – D.W. Mar 21 at 2:31
  • $\begingroup$ It was an interview question - similar to this post: stackoverflow.com/questions/41374220/… $\endgroup$ – Elliott de Launay Mar 21 at 13:11
  • $\begingroup$ The question still doesn't seem all clear. Do you want to cover all arcs with the fewest points? Or do you want to find a set of points that maximizes the ratio (number of arcs covered)/(number of points)? The latter case is trivial (just find one point that touches the most arcs), so I suppose you mean the former. $\endgroup$ – Highheath Mar 21 at 14:39
  • $\begingroup$ Yes I'd like cover all arcs with the fewest points. $\endgroup$ – Elliott de Launay Mar 21 at 15:46
  • 1
    $\begingroup$ The questions asks to optimize two quantities simultaneously: minimize the number of points, and maximize the number of arcs covered. You can't do that. There is a fundamental tradeoff: the more points you use, the more arcs you can cover. You'll need to update the question to specify a single objective function you want to optimize, before the question is answerable. If your goal is to cover all arcs with the fewest points, and it is a requirement to cover every arc, please edit the question to state that in the question. Don't leave clarifications in the comments. $\endgroup$ – D.W. Mar 21 at 17:05
1
$\begingroup$

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: "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}$?" 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.

$\endgroup$
3
  • $\begingroup$ Thank you - how would you recommend handling the case where there are arcs which wrap around the circle? (i.e. ending angle $<$ starting angle) $\endgroup$ – Elliott de Launay Mar 22 at 15:43
  • $\begingroup$ I think the easiest way is to just add 360° to the endpoint of every arc that crosses 0. Then, when you sort the arcs by starting and ending points, the two orders will agree. $\endgroup$ – Highheath Mar 22 at 17:16
  • $\begingroup$ To be more specific... I am unable to find a point on the circle that doesn't touch any arcs? (all the arcs overlap) $\endgroup$ – Elliott de Launay Mar 22 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.