# Find the longest uninterrupted arc

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.

• Welcome to PPCG! This question might get closed because this community is quite strict about the standards for winning conditions. But I hope you stick around and set more challenges! You are strongly encouraged to try them out in the sandbox, to get feedback before posting them on the main site. Commented May 13, 2018 at 13:47
• @Nathaniel: I completely understand, please let me know if there is anything I can do to improve the winning conditions. Commented May 13, 2018 at 13:55
• @Karl The only case that the arc is "interrupted" is the arc is larger than 180°, in that case just discard the arc. (<-- initially I overlooked that part because none of the test cases have such an "arc", but that can be checked in linear time) Commented May 13, 2018 at 13:59
• @Karl I believe that a good number of coders on the site would come up with an optimal solution almost instantly for this specific problem, making it largely a race to post first.
– xnor
Commented May 13, 2018 at 15:06
• I have added code-golf to the precedence. If I am proven wrong, and an optimal solution is easy to find then we can golf the optimal solution. But I still think the computational complexity is a challenge in itself. Commented May 13, 2018 at 15:13

# 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?

• An interesting answer. I see now it is easy to solve in two dimensions. Would this approach be able to work in more than two dimensions with some modifications? Or would that be best suited as another question? Commented May 13, 2018 at 16:17
• @Karl Another question. Although in more than 2D it's very unlikely that a point lies right on a line segment, and it's hard to determine due to numerical inaccuracy. Commented May 13, 2018 at 16:21
• You're right, the only approach I've found in more than 2D involves taking many samples across the arc and checking for intersections. Commented May 13, 2018 at 16:29
• @user202729 If you could post that math in an (incomplete?) answer, that would be appreciated. Commented May 18, 2018 at 19:41

# JavaScript (Node.js), O(n), 234229228 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)]
)

• How stupid I was
– l4m2
Commented May 14, 2018 at 13:07
• but in this case is array manuing still O(1)?
– l4m2
Commented May 14, 2018 at 13:10
• I still don't understand how this works, but I am willing to accept this as the answer once I have the chance to run extensive test cases. Even though it is longer than the other answer, it has a lower time complexity. Commented May 14, 2018 at 21:46
• Unless the points are always given in order around the circle, an O(n) time solution is not possible.
– user9207
Commented Jul 24, 2020 at 8:19
• @Anush I degolfed it and, after probably hours of investigation, have concluded that it's legit. It seems to work as follows. It splits the circle into n equal segments, where n is the number of points. In each segment, it records the min and max angle. The longest arc is then found by comparing the max angle of one segment to the min angle of the next nonempty segment. This utilizes the fact that the longest arc will always span multiple segments since it must always be at least 2pi/n radians in length. Very very clever solution! I hope OP doesn't mind me revealing their secrets ;P Commented Aug 18, 2020 at 7:44

# 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

• 89
Commented Aug 17, 2020 at 14:35

# JavaScript (Node.js), O(n log n)?, 130129 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

• How can it give the right answer if it sorts doubles as strings? Commented May 15, 2018 at 6:54
• @PeterTaylor Align them
– l4m2
Commented May 15, 2018 at 9:31
• Is there any reason you perform a sort (n log n) rather than just a linear search for the maximum value (O(n))? Or am I interpreting the answer wrong? Commented May 15, 2018 at 16:55
• @Karl Another sort is there, so if using sort is shorter I just use it
– l4m2
Commented May 15, 2018 at 22:50

# Wolfram Language (Mathematica), 92 bytes

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


Try it online!