Thursday, February 6, 2014

Detecting local minimum and maximum points

In this post, I introduce a new method to detect local minimum and local maximum points for a curve drawn by a discrete set of points. That means we don't have a mathematical formula for the curve and as a result we can't calculate local minimum and maximum points by differentiation to detect points of zero slope. I needed this method to detect local minimum and maximum points for a series of points (more than 30000 points) that are recorded by data acquisition system (temperatures). 

If noise is exist in values and the points don't seem to form a single continuous mathematical function (more than function, so the local maximum and minimum points may be sharp vertices), then this method is highly recommended, but with some improvements needed.

The method simply is to divide the domain into relatively large number of divisions and detect the global maximum and global minimum of each division. The method looks like the bisection method for solving equations by iteration.

From one side, the global maximum in the division should be compared with the values at the start and the end of the interval. If the global maximum is not on the interval boundaries (larger than boundary points) , then it is a local maximum. The same concept applies for the detection of the local minimum. If the local minimum is not on the interval boundaries (lower than boundary points), then it is a local minimum.

The following illustrative figure (which is not my case) is for a friction-damped vibrating mass-spring system (Coulomb dry friction model) showing the displacement of mass versus time.

The white points show the boundary points of intervals, the green points show the local maximum points, and the blue points show the local minimum points. 

For sure, some divisions will not contain local minimum or maximum points, while some will contain. Theoretically, number of divisions should be higher than the number of local minimum and maximum points.

One of the draw backs of this method is when the local maximum or minimum point is coincident with one of the interval boundaries (see the red point). This drawback can be solved by iterating with different number of subdivisions and check if there is any change or not (looks like the boundary conditions analysis in CFD). Also, it can be solved by shifting the boundaries of divisions with small amount and re-apply the method again.

Another draw back is when there are more than one point having the same maximum value. 


In case of a curve that is cycling around an average value; a smart way to detect number of divisions is to calculate the average of the curve, then the interval boundaries are composed of the following points:

- Start point of the curve
- Intersection points of average line (reference line) with the curve
- End point of the curve

The following figure shows the implementation of automatic detection of number of divisions. The reference line may not be the average value, but may also be a user-input value.