R Find the nearest convex curve "below" a set of points

Question

I have a set of points and I would like to find the convex curve that is the nearest "below" this set of points. As in the example below where every v,w points are above the qe curve. Thanks for your help.

v<-c(-1,0,0,.5,1.2,1.7,-1,1.7);w<-c(3,0,2,4,3,3.4,1,2.89)
qe<-seq(min(v),max(v),length.out=10)**2
plot(v,w)
lines(seq(min(v),max(v),length.out=10),qe)

Answer 1

What you are looking for is known as the Greatest Convex Minorant. To find it we may use the gcmlcm function from the fdrtool package.

First, we need to make sure that there is only one unique value for each x. So, we replace w by

w2 <- tapply(w, v, min)

assigning the least value of w for each value of v. (In this case there were two values at v = 0.) And that's all, our result is

result <- gcmlcm(x = as.numeric(names(w2)), y = w2, "gcm")

which we may plot with

lines(result$x.knots, result$y.knots)

giving

And it works flawlessly in more complex cases as well: