Browse Prior Art Database

Lower Envelope of a Function of One Variable

IP.com Disclosure Number: IPCOM000082555D
Original Publication Date: 1974-Dec-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 22K

Publishing Venue

IBM

Related People

Barnes, ER: AUTHOR [+3]

Abstract

Let f be defined on the interval [a,b]. The lower envelope of f is defined to be the maximal convex function g on [a,b] such that g(x)

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 59% of the total text.

Page 1 of 2

Lower Envelope of a Function of One Variable

Let f be defined on the interval [a,b]. The lower envelope of f is defined to be the maximal convex function g on [a,b] such that g(x)<f(x) for all xepsilon[a,b] (see the figure). The graph of g is also the path of minimum length joining (a,f(a)) to (b,f(b)) and lying under the graph of f.

To construct an approximation to the lower envelope of f, first se select a set of points x(1)=a<x(2)<...<x(n-1)<x(n)=b in the interval [a,b]. Then approximate f by a piecewise linear function f which agrees with f at the points x(i),i=1,...,n. It is clear that the error in this approximation can be made arbitrarily small by suitably selecting the points x(1),...,x(n). The lower envelope of f is computed as the approximation of the lower envelope of f.

An APL program can be written which will construct this approximation of the lower (or upper) envelope of any function of one variable on an interval.

The problem of determining the lower envelope of a function occurs in applications of mathematical programming, pattern recognition, and graphics. It has been demonstrated that the number of comparisons performed by this algorithm is not less than n-2 or more than 2n-5.

An informal description of the method is given below. It is clear that the only nontrivial part of the problem is to determine the set of indices i, corresponding to points x(i) where the lower envelope agrees with the function f. This set is denoted by E at the conclusio...