# a question from《learning opencv3》 chapter 14

Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14

the question is

We can find the extremal points (i.e., the two points that are farthest apart) in a closed contour of N points by comparing the distance of each point to every other point.

a. What is the complexity of such an algorithm?

b. Explain how you can do this faster.

I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is

Finding the convex hull of the contour, do the algorithm above at the convex hull .

ami i right?or better solution?

thanks！

jsxyhelu

I would look for extremal points by only comparing to the direct neighbourhood of the contour, lets say 50 points to left and 50 to right. To me it makes no sence if you have a large object, to compare the distance between a possible extremal point and the other side of the object, far away from the actual points. A convex hull would work, but in principle it will not reduce the amount of points that much.

but the " the two points that are farthest apart" must not be direct neighbourhood. sorry i did not get your idea.

ow sorry, did not read with attention. Extremal points are for me points that deviate from a general outline or trajectory, but it seems here, that they want the actual 2 points that are the farthest away from eachother. No idea how to speed that up xD

use boundingRect?

boundingRect sounds good,but boundingRect is a function of RotatedRect and we use minAreaRect to get it.

Finally minAreaRect is basd on hull