Finding the maximal convex function below a given one

I have a vector X of arguments and Y of values, both length n vectors of floats. I need to construct a vector such that (X, Yc) is a graph of a maximal convex function satisfying Yc <= Y pointwise. A naive algo that comes to my mind is O(n^2) in time, so I'm looking for something faster than that.

In math that's something we call a convex hull problem, so I have tried finding any lib in python that will do this, but they all seem to be focused on 2d or 3d problems. Any suggestions what would be the fastest way for me to find Yc?

What I have tried: I can use a scipy.spatial library to compute the 2d convex hull

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt

X = np.linspace(1, 5, 9)
Y = np.array([2, 3, 1, 4, 6, 2, 1, 4, 3])

points = np.column_stack((X, Y))
hull = ConvexHull(points)

print("Indices of points forming the convex hull:", hull.vertices)

plt.plot(X, Y, 'o')
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
plt.show()

which produces the following plot:

however, the vector Yc I need is the lower boundary of this plot, and I am not sure what's the easiest way to obtain it.

If I understand you correctly, you just need the lowest half of the convex hull. The part shown in green on the picture below:

For this, you simply build a convex hull. The convex hull will always include the leftmost and the rightmost points of your set, and those points will divide your hull into two halves. So you find these points in the convex hull, and split the hull into two halves. (One of the halves could wrap around the end of your convex hull array.) Then you need to find which half is the lowest, this can be done by many approaches, the simplest will be to calculate the average y coordinate of the two halves and choose the half that has lower average.

Also, it is possible to implement Graham algorithm so that it will directly produce the lowest half (and some implementations of the algorithm do indeed to this). You sort the points by x coordinate, and then do a simple stack-based pass. The pseudocode (adapted from Wikipedia page https://en.wikipedia.org/wiki/Graham_scan):

# The pseudocode below uses a function ccw: 
# ccw > 0 if three points make a counter-clockwise turn, 
# clockwise if ccw < 0, and collinear if ccw = 0.
# The ccw function can usually be implemented via a vector cross product

let points be the list of points
let stack = empty_stack()

sort points by x coordinate

for point in points:
    # pop the last point from the stack if we turn clockwise to reach this point
    while count stack > 1 and ccw(next_to_top(stack), top(stack), point) <= 0:
        pop stack
    push point to stack
end

In any case, you will need to somehow treat the situations when there are several leftmost or rightmost points. The exact treatment will depend on the details of your problem; because you need only the lowest half, the simplest approach will be just drop all leftmost points except the lowest of them, and similarly with the rightmost points.