A Rapid Convex Hull Algorithm for Implementing Path-Dependent Multi-Axial Fatigue

The Path-Dependent Maximum Range (PDMR) is a general-purpose multi-axial fatigue life assessment tool recently developed by Battelle researchers. The PDMR has been successfully applied to fatigue analysis of engineering components under variable amplitude, non-proportional, multiaxial fatigue loading histories. PDMR begins by seeking the maximum possible distance (or range) between any two points in the equivalent stress/strain space over a given fatigue loading history, while also identifying the associated loading path-length. The process continues recursively until each loading path has been counted. PDMR then collects the cycles calculated and the associated path-lengths for subsequent calculations of the fatigue damage. The effectiveness of the PDMR method has been validated by its ability to correlate a large amount of fatigue data. In a computerized PDMR calculation, most of the central processor unit’s (CPU) time is spent searching for the maximum range. While a brute-force search is the simplest to implement, and will always find a solution if it exists, its cost, in many practical problems, tends to grow very quickly as the size of the loading spectrum increases with O(n2) time complexity, where n is the number of spectrum data points. In this paper, Andrew’s monotone chain algorithm, a sophisticated and reliable convex hull algorithm is implemented into the PDMR to reduce the solution time. Like the widely used angular Graham Scan sort, Andrew’s monotone chain runs in O(n log n) time due to the merge-sort approach. The Rotating Caliper algorithm, which is another computational algorithm for quickly determining all antipodal pairs of vertices on a predetermined convex hull, is also introduced. Several examples have clearly demonstrated that these algorithms can be used in combination to significantly decrease the execution time for the PDMR in engineering fatigue analysis and design.