Если число элементов относительно немного, то можно просто разбить на интервалы
что бы в каждый попадало одинаковое количество элементов
перебор даже миллиона точек - довольно быстрая задача, на фоне остальных вариантов (комбинации, интерполяционные полиномы и тд).
Предлагаю мысленный эксперимент. Миллион точек, на вход подается первая и последняя точка графика. Выходит, что пара точек должна хранить информацию о всех остальных точках графика, чтобы знать, какая из них максимальная. Пусть, для примера, она окажется 500-й. Меняем первую точку на тысячную. Мы получаем новое значение максимума, определенного почти на миллионе значений, поменяв всего одну точку?
{
value: 4,
meta1: 1.234,
meta2: 4
...
}
Здесь, конечно, доля округления какая-то будет, но на сам алгоритм нахождения границ интервалов это повлиять не должно.
Данные могут иметь различное распределение. Конкретно для распределения численности населения, да, логарифмическая шкала подходит, но для других случаев, например, когда плотность распределения по центру низкая, а по краям высокая, это не подойдет