2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are points inside the circle or on it? $\endgroup$ – HEKTO Mar 25 at 21:25
  • $\begingroup$ Points on its boundary. $\endgroup$ – MohammadRostami Mar 25 at 21:49
3
$\begingroup$

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).
enter image description here

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

$\endgroup$
9
  • $\begingroup$ 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)$ $\endgroup$ – HEKTO Mar 27 at 0:16
  • $\begingroup$ @HEKTO No. It should work only with selected points per point, found in log n time per point $\endgroup$ – Joffan Mar 27 at 0:23
  • $\begingroup$ Please try to implement your algorithm programmatically and you'll see all the details you're missing $\endgroup$ – HEKTO Mar 27 at 15:52
  • $\begingroup$ @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. $\endgroup$ – Joffan Mar 27 at 23:49
  • $\begingroup$ 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 $\endgroup$ – HEKTO Mar 28 at 23:21

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.