Algorithm which finds lower bound of the epigraph of a discrete 2D curve which is not a function (i.e. fails vertical line test)

Is there an existing algorithm which solves the following problem?

Given a set of discrete values which represent the x and y Cartesian coordinates of an arbitrary curve, which is not a function (i.e. fails the vertical line test) and has an unknown analytic form, find the the corresponding discrete curve which is the lower bound of the original curve's epigraph*.

*I am unsure if the concept of an epigraph extends to curves which are not functions, but in this context, it still means the set of points lying above the curve

Example:

In the image below, the red curve is discrete, fails the vertical line test, and its initial point is located at [-5, 0]

The objective is to find the cyan curve as shown in the image below.

Is there a name for an existing algorithm which achieves this, or more generally, a name for this concept?

[Pranav Bhounsule]

It seems like the blue line is a shadow created when a ray of light shines from the top onto the red curve. Perhaps there is something in computer vision (ray tracing, shadow mapping?) that might be helpful? @John D'Errico might know....

Answer 1

[John D'Errico]

Is there an algorithm that solves it in some slick way? Not that I know of.

How would I solve it?

Treat this as a way to find the upper envelope of your curve. I don't think the function envelope, as found in the signal processing tools solves this specific problem. But it does not seem difficult to solve.

Given your curve as a sequence of (x,y) pairs, for each distinct value of x in increasing order, find all intersections of your cuve, with a vertical line at that value of x. Doug Schwarz's intersections utility does this nicely and efficiently. Find it on the file exchange. It will return All intersections of the line with your curve. At any x coordinate, choose the largest such y value returned at that location.

Lacking your curve as data, I won't write the code, but it will not be difficult. You will need to be careful about what happens at each end of the curve, but that is easy to deal with.

https://www.mathworks.com/matlabcentral/fileexchange/11837-fast-and-robust-curve-intersections?s_tid=srchtitle

[Jim]

Thanks for the consideration and suggestion.