

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

Background: I have a function in my program that takes a set of points and finds the minimum and maximum on the curve generated by those points. The thing is it is incredibly slow as it uses a while loop to figure out the min/max based on approximated error. Not completely sure what formal method this is because I did not write it myself, but I know we need a new and more efficient one.

Question: My question is what is the best and most efficient method/algorithm to finding the min max points on a curve, using C#, that is also very accurate?

About the curve: I have my Numerical Analysis book from college near me, so all I need is a method name and a nudge in the right direction. I can generate as many points as I choose to approximate the curve, but I want to keep the number of points to an efficient minimum. The curve is always in the shape of one segment of a Sin/Cos curve, but not always the same curve and will always be less that one period. The range of Theta is 0° to 359.999...° It has some phase and amplitude shift and Y will never be negative. This function/algorithm will have to run fast as it will be run every several hundred milliseconds as the curve changes.

Any suggestions are appreciated.


More info on the curve: The points are generated on mouse move. The points are a set of points based on the length of a rubber belt in a drive design with an idler, such as one like the serpentine belt in a car. The position of the idler determines the length of the belt and I get the curve [belt length(y) vs idler position(x)]. The idler in this case is a pivoting idler and will have constant circular motion. If the drive design changes the curve will change, either because the length points change, or because the range of motion of the idler has been constrained. The range of motion in the idler is potentially 0° to 359.999...° and is theta as stated above. For a slotted idler the maximum range is 1/2 of the period of the curve (easier problem).

I guess what I need is a general solver for both types of idlers, but the real issue is with the pivoting idler.

share|improve this question
How are your points being generated? I had assumed at first they were being sampled from somewhere else but now I've seen that they are changing as you move a mouse. Does this mean you have an equation that is being changed by mouse movement in some way? If you are programatically creating those points then you should have (or be able to derive) the equation for your curve... – Chris Jul 6 '10 at 16:38
@Chris, added more info in the post regarding your question. – Mike Webb Jul 6 '10 at 17:06
The min/max of sin (or cos) on some range is -1, 1 or the sin (or cos) of the endpoints. What more do you need? – sigfpe Jul 6 '10 at 21:34
@Mike: Do you have the values as array or list? – Waleed A.K. Jul 6 '10 at 21:52
It sounds like you should be able to directly calculate the min/max but unfortunately I don't fully understand the mechanics of the problem at hand - mainly because I am not sure baout what an idler is or does (and am a little fuzzy on the specifics of drive belts, etc. I'm going to drop out here unless you have time to do a diagram or something to explain to poor little me what exactly the problem looks like. ;-) Hopefully others will understand your problem better and be able to help though. :) – Chris Jul 7 '10 at 8:19
up vote 0 down vote accepted

The algorithm you should use (and the parameters you give it) depends on what your data set looks like. It sounds like you are evaluating a waveform of some physical measurement that is acquired continuously.

If so, then you need to decide whether you want to ignore local minima and maxima (eg spikes from noise in the signal). Also, you'll want some way to handle the edges of your data set. In other words, does the beginning of your data count as a maxima if it is the highest point in the current dataset but is merely coming down from a big peak in the previous one?

Canned peak detection algorithms will typically have some way to specify a threshold and also a width (to control sensitivity to spikes) and a buffer size (to handle really gradual peaks).

There are plenty of algorithms out there, just pick one or two and tweak parameters until it gives the results you expect.

share|improve this answer
Could you direct me to somewhere I can find them? Should I just google "Peak Detection Algorithms"? Also, in answer to your question, the set is very constrained. It is a waveform generated by the points [belt length vs idler position] for a belt drive with an idler attached, much like the serpentine belt drive in a car engine. – Mike Webb Jul 6 '10 at 16:11
The need for continuous update comes from the need to update the min and max when a user of my program alters the drive design on a mouse-move event. – Mike Webb Jul 6 '10 at 16:13
Also, the beginning and end both count, as you asked above. – Mike Webb Jul 6 '10 at 17:14
AFAIK peak detection algorithms include stuff similar to what bretana described in the previous post. However, a critical step that is usually performed is some type of filtering before the search. You'll want to filter the waveform just enough so that peaks which are much narrower (or much wider) than your expected peak get ignored. This way, it is possible to skip a larger number of points when taking slope measurements in your data set. Being able to take large skips in the search will make it faster. – Angelo Jul 6 '10 at 18:31

If you have a quadratic equation then the maximum or minimum will always be at the point when the differential of the equation is 0. If your quadratic equation has a formula of ax^2 + bx + c = 0 then this point will be when x = -b/2a.

Whether it is a maximum opr minimum can be determined by looking at a. If a > 0 then its a minimum and if a < 0 then its a maximum (if a = 0 then its not a quadratic).

I hope that helps. If you haven't got the equation of the curve in this sort of form could you say what you have got to work from?

Edit: question has changed so that the curve is a section of a sine curve and not a quadratic any more. This answer is therefore no longer appropriate.


With a sine curve the general equation will be y = a sin(mx+t) + c. You will never be able to exactly determine the original equation because for any solution there will be a higher frequency solution that also matches. I'm unsure currently how many points are needed to precisely calculate what a would be (which would give the min and max of the curve).

share|improve this answer
all he has is a set of points.... – Charles Bretana Jul 6 '10 at 15:34
I have a set of points to work from. As I mentioned I can generate as many of these points as I want, but I need to keep it to a minimum to keep the function efficient. – Mike Webb Jul 6 '10 at 15:37
He said that he could generate as many points as he wanted so from that I inferred he had an equation for the curve. You can get the equation for the curve from three points on that curve though so with three points you should then be able to use this method. I just need to work out how to solve the simultaneous equations in code... – Chris Jul 6 '10 at 15:37
The formula for the curve is an n-1 degree equation. For five points it's a fourth degree formula like y=ax^4+bx^3+cx^2+dx+e. You just have to derive it and determine where that is zero to find the min and max points. – Guffa Jul 6 '10 at 15:40
You have y = ax^2 + bx + c Plug in 3 points (x1, y1), (x2, y2), (x3, y3), find out a, b and c and then this answer should be what you need. – IVlad Jul 6 '10 at 15:45

Since the curve is always quadratic (and thus always convex), there should be a lot of methods available (though since I don't program in c#, I don't know if source is available). Newton's method comes to mind first but there are others (like interior point methods). For a mathematical background of these algorithms (but not their implementations, unfortunately), see this textbook (pdf). If you do use any of these methods, they'll work for other convex curves as well.

share|improve this answer
Actually, I didn't notice you only had a set of points. Not sure how applicable the answer is in this case, but check out the link if you're interested for convex optimization techniques in general. – Jan Gorzny Jul 6 '10 at 15:36
Now that I think about it it can possibly wind up being in the shape of a segment of a sin/cos curve, but always less than one whole phase. I've edited my post accordingly. – Mike Webb Jul 6 '10 at 15:50
In this case, if you can restrict the domain to a set where the function is convex (e.g. from pi to 2*pi on the standard sine graph), and find a convex optimization technique that applies to you, you can find a minimum. (And you can do a similar trick for finding the maximum.) – Jan Gorzny Jul 6 '10 at 16:00
Less than one period, I mean. – Mike Webb Jul 6 '10 at 16:00
If it's significantly less than one period and doesn't contain a point of inflection, the curve segment will always be either convex or concave. – Jan Gorzny Jul 6 '10 at 16:04

Is all you have available the set of points? And are there no restrictions on the "shape" of the function these points represent? If so, then you're probably stuck, iterating through the points will be your best bet...
Although if you have any other work to do on this set, you might want to sort it by the Y-coord for use by future processing.

(Keep both arrays around - the one you were fed as input (it's probably sorted by x-corrd ?) and the one sorted by function value(y-coord) ) ...

Edit: if you know that the curve will always be shaped "like" a portion of Sin/Cos curve, then if you know the smallest period that might be represented, you can do some optimizations by using binary search algorithm to "look" for the inflection points (where the slope (Change in Y to the left and to the right ) are of different signs. For each point examined on the left, move to the right by chunks = half the allowable period until you find the point of inflection, or the slope changes sign... Then move back by half the last change in x, until you find the point of inflection. [Do the opposite for the points on the right]

A recursive routine that examines/finds the first and last inflection point, compares them to determine which is greatest, and then recursively examines and finds, the inlfection point halfway between them, until the two points involved are less than the smallest allowable period aprt from one another, will produce some performance gains...

2nd EDIT: Since I read in yr other comment that set will never contain more than one inflection point... If this so, then just do binary search to find it.


  Check Leftmost point to see slope (Up Down or Zero)
       If Zero, done
  Check RightMost Slope 
       If Zero - Done
  If two Slopes are same sign - Done 
        - pick Bigger of two points ( - or smaller if looking for min)
  Check point in the Middle slope
     If Zero, Done
     If slope has same sign as left pt, Change Left to this Point and repeat
     If slope has same sign as right pt, Change Right to this Point and repeat
share|improve this answer
The shape will always be in the shape of some segment of a sin/cos curve, although it will always be less that one phase. I edited my post to include this info. – Mike Webb Jul 6 '10 at 15:52
Less that one period, I mean. – Mike Webb Jul 6 '10 at 16:01
@Mike, see my edit... – Charles Bretana Jul 6 '10 at 16:26
@Charles, this is what the algorithm does right now. The evaluation is good, but not efficient enough for what I need and creates lag in my program when continuously updating. – Mike Webb Jul 6 '10 at 16:38
Just finished edit. Is this what you already have ? – Charles Bretana Jul 6 '10 at 16:40

After you collected a few points (>=4) you could use a form of local search to match your points to a sine curve y = A cos(Bx+C)+D then use a simple formula based on the derivative to find the minimum. While searching, you should keep B as little as possible to avoid redundant hi-frequency solutions. Just an idea, may be very inefficient.

share|improve this answer

From the comment the input X and the output Y are arrays

"@Mike:I generate the values and put them in an array"

I suggest to use this approach. All what you need from my code is {getMaxIndex}

    private void Test()
        double[] X = SetLinearRange(0, Math.PI * 2, 1000);
        double[] Y = GetOutput(X);
        int MaxIndex = getMaxIndex(Y);
        double MaxX = X[MaxIndex];
        double MaxY = Y[MaxIndex];
    private double[] SetLinearRange(double Start, double End, int Sample)
        double Step = (End - Start) / Sample;
        double CurrentVaue = Start;
        double[] Array = new double[Sample];
        for (int Index = 0; Index < Sample; Index++)
            Array[Index] = CurrentVaue;
            CurrentVaue += Step;
        return Array;
    private double[] GetOutput(double[] X)
        double[] Array;
        Array = (from double Item in X select myFunction(Item)).ToArray();
        return Array;
    private double myFunction(double x)
        double y;
        //put any function
        y = 3 * Math.Sin(5 * x + 2);
        return y;
    private int getMaxIndex(double[] Y)
        double YM = Y.Max();
        int Index = Y.ToList().IndexOf(YM);
        return Index;

I hope that will be fast.

share|improve this answer

I'm a little confused.

If you yourself are generating the points, why not just keep track of the largest/smallest points when doing the generating?

If you have a function, like I'm sure others have pointed out, just get the derivative and solve for 0. This will give you the point(s) of min/max.

share|improve this answer

Your Answer


