Open Collections

Fazackerley, Scott Ronald

A Piecewise Linear-Quadratic (PLQ) function is used to describe data that can be represented by continuous functions with a piecewise linear domain for which the function is either linear or quadratic on, each piece of its domain [11]. While extensive work has been done with PLQ models for convex univariate functions, my work investigates the development of a two dimensional model that allows the implementation of algorithms for computing fundamental convex transforms. PLQ functions have been described in the literature, the efficient implementation of the algorithms requires the careful selection of a data structure. Initial investigation examined using a Voronoi diagram to represent the projection of the bivariate function into R2, to take advantage of efficient algorithms for the point location problem [3]. While suitable for representing a single PLQ, with operations for building a zero order model from data and evaluating the function over an irregular grid, we are uncertain if it can be extended to compute other fundamental convex transforms efficiently. In examining the Voronoi model, we were able to extend the base concept to represent the bivariate PLQ using two different representations: a tessellation-based model and a linear inequality-based model. The tessellation model is restricted to representing a PLQ with a bounded domain. The model represents data through triangular faces in a tessellation in R2 where each face is defined by its vertices and the associated function value. This model allows for the efficient evaluation over an irregular grid, the addition of two PLQ functions with bounded domains and multiplication by a scalar, but does not allow for the representation of an unbounded domain. To allow for an unbounded domain, a dual model was developed using linear inequalities to represent each face in R2. Numerical results are presented for each model and computational complexity of model components are discussed.

Text

University of British Columbia. COSC 449

Vancouver : University of British Columbia Library

10.14288/1.0052224

Arts and Sciences, Irving K. Barber School of (Okanagan); Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/