Find the longest uninterrupted arc

Question

The challenge here is to find the longest uninterruped arc around a unit circle with a random amount of points distributed in random positions around it. Here is a diagram to assist my explanation:

The red line indicates the largest arc between any two points that is not interrupted by any other points. The challenge is to find the two points on either end of the red line. The green line is simply the straight line distance.

A clarification about what interrupted means: When drawing an arc around the edge of the circle (the red line), this arc should not be intersected by any other point.

Here is a template for the function in C#:

int[] FindPair(double[][] points)
{
     return new[]{ 0, 1}; //Find the indices of the two points
}

The function should return two integers, the indices of the two points on either end of the green line.

Assumptions:

• The Length of the points array is arbitrary but more than two. In the example we have:
  points[40][]
• Each element of the points array contains the x, y position of the point, for example:
  points[i] = {x, y}
• You can assume that the distance of any given point to the origin at the centre of the circle is always 1.

Notes:

• The answer with the smallest Big O algorithm complexity wins. In case of a tie, shorter code wins.
• Bonus points for the solution to have the ability to work in more dimensions than two.
• I do have a solution, but it is very computationally expensive and only produces the correct answer around 99% of the time.
• I am not sure if the problem has a name in mathematics, or a generally accepted solution. If anyone knows of a better name for this problem so that I can have a better title, that would be helpful.

Test case 1:

Points: {
  { -0.71997 , -0.69400 },
  { 0.88564 , 0.46437 },
  { 0.78145 , -0.62397 },
  { 0.98409 , -0.17765 },
  { 0.88220 , 0.47087 },
  { 0.69938 , 0.71475 },
  { -0.89036 , -0.45526 },
  { -0.70588 , -0.70833 },
  { 0.70507 , 0.70914 },
  { -0.34971 , 0.93686 }
}

Solution:
{6, 9}

Test case 2:

Points: {
  { -0.71038 , 0.70382 },
  { 0.04882 , 0.99881 },
  { -0.53250 , -0.84643 },
  { -0.86814 , -0.49632 },
  { 0.97588 , -0.21829 },
  { 0.73581 , -0.67719 },
  { 0.88413 , -0.46724 },
  { -0.28739 , -0.95781 },
  { -0.68325 , 0.73019 },
  { 0.91879 , 0.39475 },
  { 0.65335 , 0.75706 },
  { -0.21009 , -0.97768 },
  { -0.94542 , -0.32585 },
  { 0.83207 , -0.55467 },
  { 0.99482 , 0.10170 },
  { 0.86228 , 0.50643 },
  { 0.98017 , 0.19817 },
  { 0.67520 , 0.73763 },
  { -0.03982 , -0.99921 },
  { -0.57624 , -0.81728 }
}

Solution: {0, 12}

Invalid example:

This is invalid, because when drawing an arc around the edge of the circle (the red line) between the two points connected by the green line, this arc is intersected by another point.

Answer 1

JavaScript (Node.js), O(n), 234 229 228 211 bytes

a=>(b=a.map(s=>Math.atan2(...s)/Math.PI+2),k=[],b.map(t=>d=![k[u=t*a.length|1]=t<k[u]?k[u]:t,k[--u]=t>k[u]?k[u]:t]),k.filter(t=>t).map((v,i,s)=>d=d<(t=s[i+1]||s[0]+2)-v?(T=t)-(V=v):d),[T,V].map(x=>b.indexOf(x)))

Try it online!

Assuming:

• atan2 is O(1)
• x.map, x.filter are O(n) function calls
• x.indexOf is O(n)

---

a=>(
  n=a.length,
  b=a.map(([t,u])=>Math.atan2(t,u)/Math.PI+2),    // [1, 3)
  k=[...Array(n*4)],
  b.map(t=>d=![k[u=t*n|1]=t<k[u]?k[u]:t,k[--u]=t>k[u]?k[u]:t]),
  // interval = 2/n, just enough
  k.filter(t=>t).map(
    (v,i,s)=>d=d<(t=s[i+1]||s[0]+2)-v?(T=t)-(V=v):d
  ),  // furthest
  [b.indexOf(T),b.indexOf(V)]
)

Answer 2

Python 3, O(n*log(n)), 167 bytes

import math
def f(p):p=[math.atan2(*x)for x in p];q=sorted(p);d=[b-a for a,b in zip(q,q[1:])]+[math.pi*2-q[-1]+q[0]];i=d.index(max(d));return map(p.index,(q*2)[i:i+2])

Try it online!

The sorting step takes O(n*log(n)) time, all other steps take linear time.

---

Ungolfed

import math
def f(p):
  p=[math.atan2(x, y)for x, y in p]   # convert coords to angle (radians)
  q=sorted(p)                         # sort by angle
  d=[b-a for a,b in zip(q,q[1:])]     # calculate the difference between two adjacent points
  d+=[math.pi*2-q[-1]+q[0]]           # difference between first and last point
  i=d.index(max(d))                   # where is the maximum delta?
  return map(p.index,(q*2)[i:i+2])    # where were these two points in the original list?

Answer 3

JavaScript (Node.js), O(n log n)?, 130 129 125 bytes

a=>a.map((r,i)=>[Math.atan2(...r)+6,i]).sort().map(([r,s],i,a,[p,q]=a[++i]||a[a=0])=>[p-r+!a*2*Math.PI-8,[s,q]]).sort()[0][1]

Try it online!

If the sorting is treated as O(n log n), then the whole algorithm is O(n log n); however it sorts by ASCII, so I'm not quite sure if the complexity remain