David B. Benson wrote:
> Consider a continuous, piecewise linear, monotonically
> strictly increasing (cplmsi) function on a real closed interval.
> Clearly this determines a bijection.
>
> The task is to determine a data structure for the cplmsi
> function so that both functiion values and inverse function
> values can be 'quickly' determined, using only functional
> language constructs. No imperative features allowed.
If I've understood the question correctly, your function is quantified by
a
set of points that can be linearly interpolated between. So you can
represent the sequence of points as a balanced binary tree and lookup the
bracketing points in it.
All things being equal, that is probably as efficient as you'll get.
However, it is asymptotically inefficient if the distribution of points is
strongly heterogeneous. In that case, you could either weigh subtrees
according to the length of the linear interpolations they contain, or you
could use two differently-balanced trees (one for each direction) and
weigh
by the separations in x and y respectively.
I don't know the complexity of the former but the latter should be O(log
n)
where "n" is the number of points.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
|
