# Maximize length of side of triangle from points on a circle

Given a circle with $$n$$ points, among all triangles we can make using these points, we want to find a triangle with maximum length of its shortest side in $$o(n^2)$$.

We try to make a relation between this problem and convex hull but we can't. Any help be appreciated.

• Are points inside the circle or on it? – HEKTO Mar 25 at 21:25
• Points on its boundary. – MohammadRostami Mar 25 at 21:49

You could transform the question into finding the biggest minimum angle of the triangle vertices relative to the centre.

Preparatory work:

1. Find centre $$(x_C, y_C)$$, if not already known (intersect bisectors of randomly-chosen pairs of points). $$o(1)$$

2. a) Make list of angle position for each point, $$a_i = \text{atan2}(y_i-y_C, x_i-x_C)$$. $$o(n)$$
b) Sort angle list. $$o(n \log n)$$

Main determination:

1. In succession for each point:
a) find points closest to $$\pm 120^\circ$$ points from the list, $$o(\log n)$$ per point
b) record max minimum angle with this point, update overall maximum if needed. $$o(1)$$ per point

Post process

1. Convert angle back into distance (either directly or by retrieving the indices of the appropriate points). $$o(1)$$

Explaining #3 a little more: you should find four points from the two binary searches, one either side of the $$+120^\circ$$ & $$-120^\circ$$ points. That gives you four triangles to examine for angles (differences), composed of the base point plus choices from left/right of each of the $$\pm 120^\circ$$ lines. (If any of the points are the same (few/crowded points) , there will be fewer triangles to check).

For convenience you might add extra copies of the points either side of the wraparound $$0^\circ=360^\circ$$ to avoid special cases in the search - eg. duplicate the point at (say) $$+358^\circ$$ to also be seen at $$-2^\circ$$.

• This algorithm description is vague. Could you please make it 100% clear and understandable? For example, step 3 should work with all point pairs, and their number is $O(n^2)$ – HEKTO Mar 27 at 0:16
• @HEKTO No. It should work only with selected points per point, found in log n time per point – Joffan Mar 27 at 0:23
• Please try to implement your algorithm programmatically and you'll see all the details you're missing – HEKTO Mar 27 at 15:52
• @HEKTO - I'm not missing anything. In a not-particularly-fast Python implementation, 1 million points ~15.7 s, 2 million points ~33.1 s. – Joffan Mar 27 at 23:49
• Thank you for editing your answer - it became clearer, however still sketchy. For example, you can build six triangles with four different points, closest to $\pm 120^\circ$ marks. Anyway +1 – HEKTO Mar 28 at 23:21