El problema se convierte ya en un problema matemático más que en un problema de javascript... A ver lo que se me ocurre:
Si la función no es parametrizable (es decir, no tiene forma de ecuación, son datos sin ningún sentido matemático) la cosa se vuelve complicada.
No tengo mucha idea de esto, pero a priori deberías analizar así, por ejemplo: Supongamos que tenemos miles de puntos representados en una gráfica (dices que sale tipo la del seno). Deberíamos crear rectas entre puntos correlativos (con cada pareja de puntos seguidos creamos una recta). Deberíamos saber si esa recta es creciente o decreciente (angulo de inclinación).
Entonces para todas las rectas existentes (en fin, angulos de inclinación de esas rectas) miramos a ver cuándo se pasa de inclinación negativa (decreciente) a inclinación positiva (creciente). En ese punto cambia la curvatura de la "función" y entonces tendríamos un mínimo local:
En esta imagen el crecimiento cambia en las rectas de magenta. En ese momento de cambio es cuando capturarías el punto que sería un mínimo local, osea un mínimo de los que buscas.
Parece mucho rollo pero es más facil de lo que parece porque al fin y al cabo es solo comparar angulos, que hallarás directamente con una función trigonométrica a partir de las coordenadas. Quiero decir, que aunque tengas 30000 elementos no irá tan despacio...
Dime qué te parece, supongo que habrá maneras de simplificarlo, pero no se me ha ocurrido.
Un saludo.
PD: No he contado si existen rectas horizontales, eso son pequeños detalles a utlimar..