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

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 2

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 3

APL (Dyalog Unicode), O(n), 92 bytes

L←12○⎕
x←(n←⍴L)⍴⊂⍬
L{x[⌊n×.5+⍺÷○2],←⊂⊂⍺⍵}¨⍳n
1∘⊃¨{2↑⍵⌽⍨⊃⍸(⌊/=⊢)2-/{⍵,⍵+○2}⊃¨⍵}⊃,/{⍵[⍋⊃¨⍵]}¨x

Try it online!

Takes input as a vector of complex numbers and outputs a single array of the two indices. This uses bucket sort to achieve linear complexity.

Requires ⎕IO←0

Details

L←12○⎕   ⍝ Take input to L and convert all points to their phases  -- O(n)
n←⍴L     ⍝ Set n to be the length of L                             
x←n⍴⊂⍬   ⍝ Create an array consisting of `n` empty buckets         -- O(n)
L{...}¨⍳n  ⍝ For each ⍺=element of of L, ⍵=corresponding index:    -- ×n:
  ⍺⍵         ⍝ Create an entry consisting of the two-element array ⍺ ⍵    -- O(1)
  x[...],←⊂⊂ ⍝ Append it to the correct bucket in x                       -- O(1)
  ⌊n×.5+⍺÷○2 ⍝ Map phases in [-pi, pi) to bucket indices in 0..n-1        -- O(1)
x          ⍝ Now, x is a vector of buckets,
           ⍝ each of which contains a vector of entries (phase, index)
{⍵[⍋⊃¨⍵]}¨ ⍝ Sort each bucket by phase (buckets contain 1 element on average, so this is O(1) average case per bucket)
⊃,/        ⍝ Join so we have a single sorted vector of all entries (phase, index)
{...}      ⍝ Computationally less-worrisome part now that we have the phases sorted
           ⍝ Most following lines are O(n), rest are O(1)
  ⊃¨         ⍝ Extract the phase of of each entry
  {⍵,⍵+○2}   ⍝ Add 2pi to each phase, and append (deals with wrapping around)
  2-/        ⍝ Compute the difference of each consecutive pair of phases
               ⍝ (always negative since the phases are increasing)
  ⊃⍸(⌊/=⊢)   ⍝ Find the index i of the minimum difference (most negative --- furthest)
  ⍵⌽⍨        ⍝ Rotate the original vector of (phase, index) by i
  2↑         ⍝ Take the first 2 entries
  1∘⊃¨       ⍝ Get the indices of these two entries

Answer 4

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

Answer 5

Wolfram Language (Mathematica), 92 bytes

s~Position~#-1&/@Last@(S=SortBy)[Partition[S[s=#,ArcTan@@#&],2,1,-1],EuclideanDistance@@#&]&

Try it online!