Find the longest uninterrupted arc

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?

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)]
)

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