5
\$\begingroup\$

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:

example
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:
example

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:
example

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:
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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Nathaniel May 13 '18 at 13:47
  • \$\begingroup\$ @Nathaniel: I completely understand, please let me know if there is anything I can do to improve the winning conditions. \$\endgroup\$ – Karl May 13 '18 at 13:55
  • \$\begingroup\$ @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) \$\endgroup\$ – user202729 May 13 '18 at 13:59
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – xnor May 13 '18 at 15:06
  • \$\begingroup\$ 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. \$\endgroup\$ – Karl May 13 '18 at 15:13
4
\$\begingroup\$

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)]
)
\$\endgroup\$
  • \$\begingroup\$ How stupid I was \$\endgroup\$ – l4m2 May 14 '18 at 13:07
  • \$\begingroup\$ but in this case is array manuing still O(1)? \$\endgroup\$ – l4m2 May 14 '18 at 13:10
  • \$\begingroup\$ 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. \$\endgroup\$ – Karl May 14 '18 at 21:46
5
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Karl May 13 '18 at 16:17
  • \$\begingroup\$ @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. \$\endgroup\$ – user202729 May 13 '18 at 16:21
  • \$\begingroup\$ You're right, the only approach I've found in more than 2D involves taking many samples across the arc and checking for intersections. \$\endgroup\$ – Karl May 13 '18 at 16:29
  • \$\begingroup\$ @user202729 If you could post that math in an (incomplete?) answer, that would be appreciated. \$\endgroup\$ – Karl May 18 '18 at 19:41
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ How can it give the right answer if it sorts doubles as strings? \$\endgroup\$ – Peter Taylor May 15 '18 at 6:54
  • \$\begingroup\$ @PeterTaylor Align them \$\endgroup\$ – l4m2 May 15 '18 at 9:31
  • \$\begingroup\$ 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? \$\endgroup\$ – Karl May 15 '18 at 16:55
  • \$\begingroup\$ @Karl Another sort is there, so if using sort is shorter I just use it \$\endgroup\$ – l4m2 May 15 '18 at 22:50

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.