Half-space Representations ofPiecewise Linear-Cubic ConvexFunctionsbyJeffrey Davin HattonB.Ed., The University of Alberta, 2012B.PhysEd., The University of Alberta, 2012A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFB.SC. COMPUTER SCIENCE HONOURSinIRVING K. BARBER FACULTY OF SCIENCE(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)April 2021© Jeffrey Davin Hatton, 2021AbstractThis thesis documents the data structure and functions pertaining tostoring piecewise linear-cubic convex functions in up to two dimensions assets of half-spaces. Building upon the preexisting PLCVC class structure(a representation using vertices), the PLCHC library includes a construc-tor, return function, testing function, addition function, as well as helperfunctions. Given two PLCVC instances, the vertex/edge/face style of rep-resenting a function yields challenges to adding both functions. StoringPLCVC functions’ domains as an ordered series of half-space inequalitiesfacilitates the task.While such an application takes advantage of the PLCHC structure,PLCHC is not an appropriate structure for all operations. Thus, a returnfunction, toPLCVC() is included to reconstruct an equivalent vertex repre-sentation of the function.Not all PLCVC vertices are extreme points, and are therefore arbitrarywithin restrictions. In order to unit test the return function, a custom com-parator method was developed. The purpose being to eliminate arbitraryaspects from the evaluation, as well as to compensate for MATLAB floating-point error within tolerance.iiLay SummaryFor computational mathematics, the efficiency of an algorithm can greatlyaffect runtime, and the manner in which information is stored can affect thealgorithm. In the case of surface functions with a polyhedral piecewise do-main: storing vertices, edges, and faces facilitate the algorithm for determin-ing convexity. This approach is less efficient for adding two such functionstogether.This thesis presents a MATLAB library which converts a vertex/edge/facerepresentation of a function to a collection of inequalities. Additionally, anaddition algorithm is included, as is a reverse conversion. This structurefacilitates addition of two functions.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . viiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Preexisting Material: PLCVC . . . . . . . . . . . . 32.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 PLCVC Existing Methods Relevant to PLCHC . . . . . . . . 42.2.1 Constructor . . . . . . . . . . . . . . . . . . . . . . . . 42.2.2 createP . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2.3 createDom . . . . . . . . . . . . . . . . . . . . . . . . 5Chapter 3: PLCHC . . . . . . . . . . . . . . . . . . . . . . . . . 63.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2 Constructor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.3 toPLCVC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.4 Add . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Chapter 4: Comparator Methods . . . . . . . . . . . . . . . . . 164.1 Rational . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.2 Defining Equality . . . . . . . . . . . . . . . . . . . . . . . . . 164.3 hasSameDomain . . . . . . . . . . . . . . . . . . . . . . . . . 16ivTABLE OF CONTENTS4.3.1 hasFullDomain . . . . . . . . . . . . . . . . . . . . . . 184.4 isEqual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.4.1 hasOverlapWithinTolerance . . . . . . . . . . . . . . . 21Chapter 5: Testing . . . . . . . . . . . . . . . . . . . . . . . . . . 235.1 Unit testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.2 Test Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . 23Chapter 6: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 286.1 Other Considerations . . . . . . . . . . . . . . . . . . . . . . . 286.2 Improvements needed . . . . . . . . . . . . . . . . . . . . . . 286.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30vList of FiguresFigure 2.1 PLCVC representation . . . . . . . . . . . . . . . . . 4Figure 3.1 Two-dimensional PLC function in PLCVC and PLCHCrepresentations . . . . . . . . . . . . . . . . . . . . . . 7Figure 3.2 A segment represented in PLCVC and PLCHC . . . . 9Figure 3.3 A ray represented in PLCVC and PLCHC . . . . . . 9Figure 3.4 Example of 0-dimensional PLCHC domain . . . . . . 11Figure 3.5 PLCVC created directly from polyhedral sets or usingtoPLCVC . . . . . . . . . . . . . . . . . . . . . . . . . 12Figure 3.6 Example of worst case leading to quadratic runtime . 13Figure 3.7 Two bounded faces compared for intersection - thegreen domain is the intersection of blue and yellowfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Figure 3.8 One full domain function’s coefficients added to afunction with multiple pieces; result is displayed . . . 15Figure 3.9 The two PLCVC functions with two polyhedral setsare added, and each set intersection results in a poly-hedral set . . . . . . . . . . . . . . . . . . . . . . . . . 15Figure 4.1 Two PLCVC functions with polyhedral sets stored indifferent order . . . . . . . . . . . . . . . . . . . . . . 17Figure 4.2 The same PLC function could be represented as asingle face, or as two faces with the same coefficients 17Figure 4.3 These two PLCVC functions would not be consideredas having the same domain unless the tolerance wasabove 0.3 . . . . . . . . . . . . . . . . . . . . . . . . . 18Figure 4.4 A bounding box for unbounded polyhedral sets in or-der to address floating point error . . . . . . . . . . . 19Figure 4.5 Examples of PLCVC functions with full domains . . . 19viLIST OF FIGURESFigure 4.6 Two polyshapes (blue and yellow) representing poly-hedral sets which would count as overlapping (green)for tolerance of 0.25 but not a tolerance of 0.6 . . . . 22Figure 5.1 Unit test for strict equality . . . . . . . . . . . . . . . 24Figure 5.2 Unit test for strict equality ignoring floating point error 24Figure 5.3 Unit test using PLCHC.isEqual() . . . . . . . . . . . 25Figure 5.4 Example of unreachable lines via unit tests - theselines are meant to offer a relevant message for unex-pected input . . . . . . . . . . . . . . . . . . . . . . . 25Figure 5.5 Test Coverage Results . . . . . . . . . . . . . . . . . . 27viiAcknowledgementsI would like to thank the following people who have helped me undertakethis research, without whom I would not have been able to complete thisresearch:My supervisor Dr. Yves Lucet., for his support in all aspects of thisthesis, for his knowledge towards the project, for his patience regarding allstumbles along the way, and for his enthusiasm when a stimulating questionshows progress.My fellow honours colleague Aaron Mahnic, for his insight and assistancein handling a challenging aspect of the project.Master’s student Zeneb Kagdiwala, for providing perspective. Meetingsomeone likely to further the project inspires me to write code of the highestpossible quality.viiiDedicationI would like to dedicate my work in this thesis to my family. To myparents especially whose support during such a challenging year can be de-scribed as nothing short of magical.ixChapter 1IntroductionComputational Convex Analysis (CCA) has been shown to be neededby fields such as network flows, thermodynamics, robot navigation, andmedical imaging [Luc10]. The algorithms developed offer powerful toolsfor the above fields and more. In Network flows, convex optimization as-sists with the minimum-cost flow problem [SFL19]. Proving that a materialmodel fulfills the second law of thermodynamics is aided significantly byconvex analysis [PE13], and Fast Legendre Transform (FLT) is used com-pute tabulated Equation Of State (EOS) for fluids with phase transition[HM11]. Non-convex environment planning can be solved as a series of con-vex optimization problems [SDH+14], while non-smooth environments canbe navigated using distance transforms, a special case of the Moreau en-velope [Luc10]. Medical imaging uses the Legendre-Fenchel transform toidentify discontinuities between adjacent pixels (such as edges of a tissuetear) [Luc10].Computer-Aided Convex Analysis focuses on visualizing operators whenapplied to functions of typically one or two variables [HL18]. Concepts suchas the proximal average would otherwise be challenging to compute numeri-cally, as it is a composition of multiple operators [GL11]. The computation iscurrently performed using algorithms relating to piecewise linear-quadratic(PLQ) functions [GL11].Piecewise linear-cubic (PLC) functions are the object of this projectbased thesis. According to [SL19], PLC functions are defined as piecewisepolynomial functions with a polyhedral domain, such that on each polyhe-dral set, the function is defined by a cubic expression. The CCA toolboxalready has the PLCVC class for representing a PLC function with a datastructure and determining convexity. Other operations such as the additionoperator can be performed with alternative structures. The PLCHC classwas developed for representing PLC functions to facilitate the add operator.The addition of two PLC functions is the purpose of this project. ThePLCHC class MATLAB library was developed as part of the CCA toolboxto follow a proposed algorithm for adding two PLC functions [GJL14]. Thealgorithm involves returning a PLC function after using the map overlay1Chapter 1. Introductionalgorithm, such as is seen in [dBvKOS97], to overlay the features of twofunctions across each other.2Chapter 2Preexisting Material:PLCVCPLCVC refers to representing a piecewise linear-cubic function with ver-tices and coefficients. Vertices are (x,y)-value coordinate pairs. Each vertexis an extreme points for describing the shape of each piece of a PLC functionp. For further description, relations between vertices allow for describing theedges along a domain, and relations between edges and sets of coefficientsdescribe the faces of p. In Figure 2.1, we show the domain, the 3-dimensionalvisualization, and an example of a polyhedral set’s edge.2.1 Data StructurePLCVC has the following properties for a function p:− The properties nv,ne,nf each store an integer for the number of ver-tices, edges, and faces in p respectively.− The property V is a nv × 2 matrix storing vertices list for p.− E is a ne × 3 matrix storing two indexes and a boolean. E(i, :) =[i1, i2, b] means edge i is a directed edge from V(i1,:) to V(i2,:). Theboolean b equals 1 for a segment and 0 for a ray.− The f property stores an nf × 10 matrix. The matrix f stores thecoefficients for the 10 terms of a bivariate cubic function.− The F property is a ne× 2 matrix that describes the adjacent faces ofan edge.− The P property is a cell array of length nf . It represents an adjacencylist. Each element P{i} is an array of indices k with 1 > |k| > ne(i)where ne(i) is the number of edges in face i. If k > 0, then the facelies on the right of the edge; otherwise k > 0. The edge indices areordered to obtain a unique representation.32.2. PLCVC Existing Methods Relevant to PLCHC(a) Domain of a PLCVC function (b) PLCVC function with 3D vi-sualizationFigure 2.1: PLCVC representation− The dom property is a struct with properties dim, P , and isConvex.The property dom.dim is the dimension of the domain. If not empty,dom.P stores the indexes of the domain.2.2 PLCVC Existing Methods Relevant toPLCHC2.2.1 ConstructorThe constructor takes a variable number of parameters as input depend-ing on whether the domain of the function is 0, 1, or 2 dimensions, as well asdepending on whether the domain of the function has vertices or edges. Therows of each input array do not need to be sorted. The values nv, ne, nf ,P , and dom are not passed as parameters, but are instead calculated withinthe constructor. If a function is full domain and has no vertices or edges,the only parameter needed is a single array representing the coefficients ofthe function. Otherwise, four arrays representing V , E, f , and F must bepassed - even if they are empty. The dimension of a PLCVC function iscalculated from the number of edges and adjacent faces provided.For example, for the following polyhedral sets and coefficients describing42.2. PLCVC Existing Methods Relevant to PLCHCa PLC function,V =−1 −10 −1−1 −0.50 01 0E =1 2 12 5 11 3 12 4 13 4 14 5 1 , F =1 02 00 11 20 10 2 , f =[0 0 0 0 0 01 0 0 0 0 0],hhe following properties would be created, nv = 5, ne = 6, nf = 2,P ={[−1 3 5 4][−2 4 6]}, dom =dim : 2P : [1, 2,−6,−5,−3]isConvex : 1 .The PLCVC constructor is robust, checking for many possible flaws inhow the parameters have been passed and how they relate to each other.For example, if the number of sets of coefficients does not match the numberof calculated faces, an error is returned.2.2.2 createPThis method is called in the constructor and is responsible for creatingan ordered list of edges for each face. The PLCHC library takes advantageof this order and maintains it.2.2.3 createDomThis method creates the dom property struct. Most notably it calcu-lates whether a set of inputs are describing a 0-dimensional (single vertex),1-dimensional (edges without faces), or 2 dimensional (PLC functions withfaces). The dimension property is maintained in PLCHC. The dom.P prop-erty describes the entire domain of p as a single polyhedral set.5Chapter 3PLCHC3.1 Data StructureThe PLCHC class offers an alternative to the vertex based representationof a piecewise linear-cubic function. The H stands for half-space, and refersto the representation of faces as the set of (x,y) coordinate pairs satisfying aset of linear inequalities - in contrast to storing vertices for PLCVC. PLCHChas the following properties for a function p:− nh stores an integer for the number of polyhedral sets defining thedomain of p.− H is a cell array of length nh. For each polyhedral set in p, an nh ×3 matrix stores the coefficients of linear inequalities to describe theset. The inequalities are sorted to always involve travelling clockwisearound the set; H(k, :) = [a, b, c] stores the half-space ax+ by+ c ≥ 0.− The dim is an integer describing the dimension of the domain of p.This is stored from the PLCV C.dom property. Values can be 0, 1, or2.3.2 ConstructorThe PLCHC constructor takes a PLCVC instance as input. The ma-trix f is the same for both classes PLCHC and PLCVC. For each ith setof coefficients in PLCV C.f , PLCHC stores a corresponding set of linearinequalities enclosing the domain for fi. The PLCHC constructor requireshandling for 3 cases based on the dimension of the input PLCVC function.When the input’s PLCV C.dim = 2, the input function has faces. ThePLCV C.P property stores ordered edges for travelling clockwise aroundeach face. For each face, the constructor iterates over each edge and convertsthe oriented edge to a half-space as visualized in Figure 3.1 and as describedwith Algorithm 1.63.2. Constructor(a) Figure on the left side is a PLCfunction in vertex representation.(b) Figure on the right side is aPLC function in half-space repre-sentation.Figure 3.1: Two-dimensional PLC function in PLCVC and PLCHC repre-sentationsThe order of edges found in the input’s PLCV C.P property are main-tained in H. Each set of inequalities for a face is ordered such that consecutiveinequalities represent adjacent edges along a face.Algorithm 1: Two-dimensional PLCHC constructioninitialization;foreach face doforeach edge along face doorient the half-space;obtain the edge information;obtain vertices from edge;linearInequalityCoefficients ←− PLCHC.lineEquation(verticesfrom edge);set coefficients in H;endend73.2. ConstructorFor example, consider a PLCVC instance with the following properties:V =−1 −10 −1−1 −0.50 01 0E =1 2 12 5 11 3 12 4 13 4 14 5 1 , F =1 02 00 11 20 10 2 , f =[0 0 0 0 0 01 0 0 0 0 0],nv = 5, ne = 6, nf = 2,P ={[−1 3 5 4][−2 4 6]}, dom =dim : 2P : [1, 2,−6,−5,−3]isConvex : 1 .The PLCHC constructor computesnh = 2, H =0 1 10.5 0 0.50.5 −1 0−1 0 0−1 1 11 0 00 −1 0, f =[0 0 0 0 0 01 0 0 0 0 0], dim = 2.When PLCVC.dim = 1, the function has a chain of edges. For all iedges, each edge is converted into a 4x4 matrix of linear inequalities as inFigure 3.2 or 4x3 matrix of linear inequalities as in Figure 3.3. The processis further illustrated in Algorithm 2.For example, given the polyhedral set of a PLCVC instance describinga single line segment:V =[0 01 0], E =[1 2 1], F = [ ], f =[1 0 0 0 0 0],the associated PLCVC instance isnh = 2, H =0 1 10.5 0 0.50.5 −1 0−1 0 0−1 1 11 0 00 −1 0, f =[0 0 0 0 0 01 0 0 0 0 0], dim = 2.83.2. ConstructorFigure 3.2: A segment represented in PLCVC and PLCHCFigure 3.3: A ray represented in PLCVC and PLCHC93.3. toPLCVCAlgorithm 2: One-dimensional PLCHC constructioninitialization;foreach edge doif edge is a segment theninitialize a matrix for 4 half-spaces;obtain vertices from edge;linearInequalityCoefficients ←− PLCHC.lineEquation(verticesfrom edge);set both half-spaces along the line;set both half-spaces perpendicular to the line;else edge is a rayinitialize a matrix for 3 half-spaces;obtain vertices from edge;linearInequalityCoefficients ←− PLCHC.lineEquation(verticesfrom edge);set both half-spaces along the line in H;set half-space perpendicular to the line in H;endendWhen PLCV C.dim = 0, the function has a single vertex. As shown inAlgorithm 3, PLCHC stores a single point as a 4x3 matrix such that eachrow in the matrix is the negative of another row, thus reducing the set toa single point as seen in Figure 3.4. While it was possible to store a needlefunction uniquely with only 3 half-spaces, the use of 4 minimizes the needfor using the PLCHC.lineEquation() and PLCHC.intersection() functions,thereby limiting risk of floating point error.Algorithm 3: Zero-dimensional PLCHC constructioninitialization;create 4 half-spaces which enclose a single point;obtain vertex of needle function;translate half-spaces to enclose vertex;3.3 toPLCVCtoPLCVC() takes a PLCHC function and converts it to a PLCVC rep-resentation. Similar to the PLCHC, 0-dimensional and 1-dimensional func-tions are handled as edge cases. 2-dimensional functions also have two cases:bounded and unbounded functions as seen in Algorithm 4.103.3. toPLCVCFigure 3.4: Example of 0-dimensional PLCHC domainIn toPLCVC(), the approach for determining boundedness was to usethe inherent orderedness of PLCHC.H face edges in order to compare thefirst and last inequalities. If the face is unbounded, then the inequalitieswould be representing rays. The rays would either be parallel or with anintersection that is outside the face’s domain.In all cases, toPLCVC() iterates over all sets of half-spaces. For each in-equality, the relationships to other inequalities such as adjacent inequalitiesfor vertices are calculated. As vertices are obtained in pairs, they are addedto a Vertex list if not already in the list, and the pair of vertices are usedto add an edge to an edge list if not already found in the list. Using thedirection of the edge, the adjacency list PLCVC.F is updated. Figure 3.5shows the original PLCVC instance compared to the PLCVC instance fromtoPLCVC. If dim = 1 then each polyhedral set adds an edge, and no faceadjacencies are added. If dim = 0 then a single needle function is returned,with neither edges nor face adjacencies.The function coefficients list remains unchanged. Once all iterationscomplete, and the vertex, edge, coefficients, and adjacency lists are created,113.3. toPLCVC(a) A PLCVC function created di-rectly from a polyhedral set(b) A PLCVC function created byPLCHC.toPLCVC()Figure 3.5: PLCVC created directly from polyhedral sets or using toPLCVCthe PLCVC constructor is called and the PLCVC instance is returned.Algorithm 4: Two-dimensional PLCHC to PLCVC conversion.initialization;foreach half-space set doif set is bounded thenconvert each half-space to a pair of vertices for intersectionswith both adjacent half-spaces;add vertices to V list;add indexes of vertices to E list as segments;update face adjacencies;else set is unboundedconvert each half-space to a pair of vertices for intersectionswith both adjacent half-spaces;add vertices to V list;first and last half spaces are converted to rays;remaining half-spaces are converted to segments;add edges to E list;update face adjacencies;endend123.4. AddFigure 3.6: Example of worst case leading to quadratic runtime3.4 AddThe add method is an efficient algorithm for adding two PLC functions.Given two PLC functions, add() has O(n2) runtime complexity. Figure 3.6demonstrates a simple example of the worst case runtime. Given that eachpair of faces may have domain intersection, each combination of faces mustbe considered. The algorithm iterates over each combination of faces usingtwo nested loops.The following are cases to consider in order to return a valid completerepresentation of the addition of two functions:1. If both functions have full domains with one face there are no featuresto overlay.2. If one function has a full domain with a single face, there are no fea-tures to overlay across the features of the second function. The struc-ture of the second function is returned with the coefficients of bothfunctions added. Figure 3.8 demonstrates the coefficients of a full do-main function added to the coefficients of each polyhedral set in asecond PLC function.3. If both functions have one or more partial domain faces, then - as seen133.4. Addin Algorithm 5 - for each face in p1 a comparison must occur with eachface in p2. This case has only been implemented for functions withexclusively bounded faces thus far. For each comparison, both facescan be converted to polyShapes. For each pair of polyShapes, if anintersection exists, the intersection, shown in Figure 3.7, is a polyShapewhich is then converted back into vertex, edge, and face adjacency liststo describe a polyhedral set. The coefficients for the resulting face arethe sum of coefficients from the compared faces. Once all face pairshave been compared, the polyhedral sets are passed to the PLCVCconstructor and a PLCVC instance is returned. The domains of twoinput functions and the result are demonstrated in Figure 3.9.Algorithm 5: Add Algorithm for bounded PLC functionsinitialization;foreach face in P1 doforeach face in P2 doconvert both faces to polyShapes;if overlap exists thenadd coefficients of both faces;add new coefficients to f list;convert polyShape intersection to polyShape vertex listforeach vertex in polyShape vertex list doadd vertices to V list;add indexes of vertices to E list as segments;update face adjacencies;endendendendUnbounded faces are not currently handled. One approach involves setcomparison by converting the PLCVC functions to PLCHC and comparingsets of half-spaces for a resulting domain. The new PLCHC face would thenneed to be converted back to vertex representation. The order of edges mustbe sorted before returning the vertex, edge, and face adjacency lists.143.4. AddFigure 3.7: Two bounded faces compared for intersection - the green domainis the intersection of blue and yellow facesFigure 3.8: One full domain function’s coefficients added to a function withmultiple pieces; result is displayedFigure 3.9: The two PLCVC functions with two polyhedral sets are added,and each set intersection results in a polyhedral set15Chapter 4Comparator Methods4.1 RationalUnit testing the toPLCVC() and add() methods was not possible withexisting comparator methods in MATLAB. Strictly equating two PLCVCfunctions would require having all values to be equal, and in the same order.Given floating point error, that vertex and edge lists are not sorted witha particular order, that the same PLC function could be represented withdifferent numbers of faces, and that some vertices are not extreme points andthus partially arbitrarily chosen, testing for strict equality was not possible.MATLAB can handle floating point error in testing using tolerance, but hasno way of accounting for different Polyhedral set orders such as in Figure 4.1or values such as in Figure 4.2.4.2 Defining EqualityFundamentally, defining equality between two PLC functions involvesproving that they represent the same function. For each (x,y) coordinatepair, P1 and P2 must be shown to have the same value. This involvescomparing coefficients for sets of coordinate pairs.4.3 hasSameDomainThe first requirement for equality is that two PLCVC functions have thesame domain. There are three cases to consider:1. The PLC functions may have a full domain. For this, a separatefunction was created to determine if a function is full domain. If onefunction has a full domain and the other does not, then they do nothave the same domain.2. The PLCVC functions may have a fully bounded polyhedral set. Forthis case, the perimeter of the functions (PLCV C.dom.P ) are con-164.3. hasSameDomainFigure 4.1: Two PLCVC functions with polyhedral sets stored in differentorderFigure 4.2: The same PLC function could be represented as a single face,or as two faces with the same coefficients174.3. hasSameDomainFigure 4.3: These two PLCVC functions would not be considered as havingthe same domain unless the tolerance was above 0.3verted into polyShapes and compared using polyShape.difference(). Ifthe difference exceeds a provided tolerance the functions do not havethe same domain - visualized in Figure 4.3.3. The PLC functions have polyhedral sets which are unbounded butnot finitely defined across the full domain. Handling these domainsrequired bounding the polyhedral sets with a bounding box and com-paring the sets as bounded functions. To ensure that critical points areincluded, the bounding box encloses all vertices from both functions asseen in Figure 4.4. Without bounding the function, any floating pointerror could become trivially large as edges diverge. The comparisonsare still between bounded polyShapes as in Figure 4.3.4.3.1 hasFullDomainThis method takes a PLCVC instance and evaluates if it has a full do-main or not. As shown in Algorithm 6, hasFullDomain() returns true if thefunction has one full domain face, as seen in Figure 4.5(a), or multiple facesthat combine to form a full domain Figure 4.5(b). Using the PLCVC.Fproperty, if the function has any edges, the adjacency list is evaluated. Ifany edge is adjacent to face 0 on either side, the function returns false.184.3. hasSameDomainFigure 4.4: A bounding box for unbounded polyhedral sets in order to ad-dress floating point error(a) A full PLCVC function withonly one polyhedral set(b) A full PLCVC function withmultiple polyhedral setsFigure 4.5: Examples of PLCVC functions with full domains194.4. isEqualAlgorithm 6: hasFullDomain for a given function pif P has no edges thenif P has one vertex thenResult: not fullelseResult: fullendelseforeach edge doif edge is not adjacent to a face on either side thenResult: not fullendendResult: fullend4.4 isEqualFor two PLC functions P1 and P2, isEqual() first checks that P1 andP2 have the same domain using the hasSameDomain() method. Once thedomains have been determined as equal, each pair of faces between P1 andP2 is iterated over. For n1 and n2 faces, isEqual() has O(n1n2) runtimecomplexity as there are a quadratic number of possible overlaps. Therewere two cases:1. As seen in Algorithm 7, if either function has a full domain with noedges or vertices, all faces overlap. The full function’s coefficients arecompared to coefficients for each faces of the other function. If anymismatch is found, return false.2. As seen in Algorithm 8, if neither function is a full domain single face,then each pair of faces are converted into polyShapes for compari-son. Each pair are compared using the hasOverlapWithinTolerance()method. If overlap is determined to exist, then their coefficients mustbe the same. If they are not, isEqual() returns false. If all comparisonshave either no overlap or have the same coefficients, then return true.204.4. isEqualAlgorithm 7: PLC comparison when one function has no edges orverticesforeach face in P1 doforeach face in P2 doif P1 or P2 has no edges and no vertices thenif coefficients do not match thenResult: P1 and P2 are not the same PLC functionsendendendendResult: P1 and P2 are the same PLC functionsAlgorithm 8: PLC comparison for faces with edgesforeach face in P1 doforeach face in P2 dopgon1 ←− PLCHC.faceToPolyShape(P1, face index);pgon2 ←− PLCHC.faceToPolyShape(P2, face index);if pgon1 or pgon2 have overlap thenif coefficients do not match thenResult: P1 and P2 are not the same PLC functionsendendendendResult: P1 and P2 are the same PLC functions4.4.1 hasOverlapWithinToleranceTaking two polyshapes pgon1 and pgon2, this method uses polyShape.difference()twice (as the subtraction is not commutative) to create two new polyshapespgon3 and pgon4. The areas of both pgon3 and pgon4 are added as the totaldifference. If the total difference, as a fraction of pgon1 or pgon2, exceeds thetolerance provided then there is not considered to be overlap - as visualized214.4. isEqualFigure 4.6: Two polyshapes (blue and yellow) representing polyhedral setswhich would count as overlapping (green) for tolerance of 0.25 but not atolerance of 0.6in Figure 4.6.Algorithm 9: Checking for overlap between two polyShapesA1 ←− area(pgon1);A2 ←− area(pgon2);if pgon1 or pgon2 intersect thenoverlap ←− intersect(pgon1, pgon2);overlapArea ←− area(overlap);ratio1 ←− overlapArea/A1;ratio2 ←− overlapArea/A2;if ratio1 or ratio2 ≥ tolerance thenResult: P1 and P2 overlapendendResult: P1 and P2 do not overlap22Chapter 5TestingValidating the quality of the library is necessary for it to be publicly us-able. Unit test writing involved careful consideration regarding the validityof the tests as well as the coverage that they offer.5.1 Unit testingPrior to considering a method complete, it must have been unit tested.Initial unit test sets are written in advance prior to the development of amethod. These initial test are written to test the broad use cases of themethod. As a method nears completion, new cases may be observed asneeding handling. Such new cases require additional tests which are addedbefore a method is used.Initially, while the methods developed could expect unique representa-tions for all values, the expected values could be compared for strict equality.The constructor’s unit tests are designed to expect precise structure and val-ues as seen in Figure 5.1. Some tests encounter issues with floating pointerror alone, which is addressable using MATLAB’s built in testing toleranceas seen in Figure 5.2.For unit testing the toPLCVC() and add() methods, isEqual() was usedto evaluate that the returned PLCVC instance represented the correct PLCfunction.5.2 Test CoverageMATLAB has a built in profiler for code analysis. When run alongside atest file, a test coverage report may be generated. For each method accessedwithin the test file, the percentage of lines of code executed is calculated. Ahigher value implies the unit tests have breadth.Full method coverage is generally desirable, within reason. Writing anextensive unit test for a single line of code may not be efficient as it mayoffer diminishing returns. Sometimes testing particular lines in-depth with235.2. Test CoverageFigure 5.1: Unit test for strict equalityFigure 5.2: Unit test for strict equality ignoring floating point error245.2. Test CoverageFigure 5.3: Unit test using PLCHC.isEqual()Figure 5.4: Example of unreachable lines via unit tests - these lines aremeant to offer a relevant message for unexpected input255.2. Test Coveragemultiple tests is more important for the rigorous validation of a method.Coverage of less than 100 percent may also be acceptable if particular linesare not counted as executed such as end lines or intentionally unreachableerror messages as seen in Figure 5.4. As seen in Figure 5.5 the 98 unit testscurrently cover 98.2% of the PLCHC library.265.2. Test CoverageFigure 5.5: Test Coverage Results27Chapter 6ConclusionThis project has made advances in progressing the ability to computa-tionally represent and interact with bivariate PLC functions, most notablythe ability to compare two functions, the ability to add two functions, andthe ability to convert between a vertex representation and a half-space rep-resentation. Given this progress, there are some areas identified as needingfurther work.6.1 Other ConsiderationsThe PLCHC library was written such that all methods were in one file.This approach was selected in order to leave the PLCVC library untouchedas the PLCVC library was being used by multiple projects. Otherwise therewas the risk of conflicts. Some of the methods in PLCHC pertain exclusivelyto PLCVC instances. It may be more intuitive to refactor these methods,such as PLCHC.isEqual(), to migrate them into the PLCVC library. Thiswould make their usage more intuitive.6.2 Improvements neededThere are some edge cases which should be further handled and tested1. This project predominantly focused on developing the PLCHC li-brary for the broadest use cases. Two-dimensional PLC functionswere emphasized. While some PLCHC methods handle cases withlower dimensions such as the constructor and the reverse conversiontoPLCVC(), identifying and handling each possible degenerate case inall methods was not stressed. Implementation of such handling wouldimprove the robustness of the data structure as well as the libraryfunctionality as a whole.2. The add() method was the purpose of this project. Laying the foun-dation for an efficient algorithm required the majority of PLCHC li-286.3. Future Workbrary to be implemented and tested beforehand. As such, one of thecore cases of a two dimensional PLC addition operation was not im-plemented. It will be necessary to determine an algorithm withinPLCHC.add() for handling the case where both PLCVC functions havenon-full domain faces, but at least one of the functions has unboundedfaces.6.3 Future Work1. The PLCHC constructor was implemented such that the orderednessof the edges associated with a face was maintained. This assumes theorder exists beforehand within the PLCVC instance taken as input.An implication of this is that a polyhedral set describing a PLC func-tion can not be used to construct a PLCHC instance directly. Anextension to the PLCHC library could involve providing the orderinginternally. The half-spaces could be ordered even if the PLCHC con-structor is only provided vertex, edge, coefficient and adjacency lists -thus removing the PLCVC instance as required input.2. The add() and isEqual() methods provided an efficient framework foralgorithms involving comparing faces between two PLC functions. Anextension to this is that a max() or min() method would require thesame framework. A max() function would also involve comparing allcombinations of faces. While the framework is similar - requiring cal-culating intersections, the max() function would also require an evalu-ation of the coefficients across a domain, as there is no guarantee thatone function is the maximum across the entire intersection.29Bibliography[dBvKOS97] Mark de Berg, Marc van Kreveld, Mark Overmars, and OtfriedSchwarzkopf. Computational Geometry, pages 19–44. SpringerBerlin Heidelberg, Berlin, Heidelberg, 1997. → pages 2[GJL14] B. Gardiner, K. Jakee, and Y. Lucet. Computing the par-tial conjugate of convex piecewise linear-quadratic bivari-ate functions. Computational Optimization and Applications,58:249–272, 2014. → pages 1[GL11] Bryan Gardiner and Yves Lucet. Graph-Matrix Calculus forComputational Convex Analysis, pages 243–259. Springer NewYork, New York, NY, 2011. → pages 1[HL18] Tasnuva Haque and Yves Lucet. A linear-time algorithm tocompute the conjugate of convex piecewise linear-quadraticbivariate functions. Computational Optimization and Applica-tions, 70(2):593–613, 06 2018. → pages 1[HM11] P. Helluy and H. Mathis. Pressure laws and fast legendretransform. Mathematical models & methods in applied sci-ences, 21(4):745–775, 2011. → pages 1[Luc10] Yves Lucet. What shape is your conjugate? a survey of com-putational convex analysis and its applications. SIAM Review,52(3):505–542, 2010. → pages 1[PE13] Nelly Point and Silvano Erlicher. Convex analysis and ther-modynamics. Kinetic & related models, 6(4):945–954, 2013. →pages 1[SDH+14] John Schulman, Yan Duan, Jonathan Ho, Alex Lee, IbrahimAwwal, Henry Bradlow, Jia Pan, Sachin Patil, Ken Goldberg,and Pieter Abbeel. Motion planning with sequential convexoptimization and convex collision checking. The International30“Chapter 7 Bibliography”-¿”Bibliography”Journal of Robotics Research, 33(9):1251–1270, 2014. → pages1[SFL19] Somayeh Sojoudi, Salar Fattahi, and Javad Lavaei. Convex-ification of generalized network flow problem. MathematicalProgramming, 173(1-2):353–391, 01 2019. → pages 1[SL19] Shambhavi Singh and Yves Lucet. Linear-time convexity testfor low-order piecewise polynomials. SIAM Journal on Opti-mization, 31(1):972–990, 2019. → pages 131
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Undergraduate Research /
- Half-space Representations of Piecewise Linear-Cubic...
Open Collections
UBC Undergraduate Research
Half-space Representations of Piecewise Linear-Cubic Convex Functions Hatton, Jeffrey Davin 2021-04
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Half-space Representations of Piecewise Linear-Cubic Convex Functions |
Creator |
Hatton, Jeffrey Davin |
Date Issued | 2021-04 |
Description | This thesis documents the data structure and functions pertaining to storing piecewise linear-cubic convex functions in up to two dimensions as sets of half-spaces. Building upon the preexisting PLCVC class structure (a representation using vertices), the PLCHC library includes a constructor, return function, testing function, addition function, as well as helper functions. Given two PLCVC instances, the vertex/edge/face style of representing a function yields challenges to adding both functions. Storing PLCVC functions' domains as an ordered series of half-space inequalities facilitates the task. While such an application takes advantage of the PLCHC structure, PLCHC is not an appropriate structure for all operations. Thus, a return function, toPLCVC() is included to reconstruct an equivalent vertex representation of the function. Not all PLCVC vertices are extreme points, and are therefore arbitrary within restrictions. In order to unit test the return function, a custom comparator method was developed. The purpose being to eliminate arbitrary aspects from the evaluation, as well as to compensate for MATLAB floating point error within tolerance. |
Subject |
data structure Linear-Cubic Convex Functions |
Genre |
Graduating Project |
Type |
Text |
Language | eng |
Series |
University of British Columbia. COSC 449 |
Date Available | 2021-06-07 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0398276 |
URI | http://hdl.handle.net/2429/78550 |
Affiliation |
Science, Irving K. Barber Faculty of (Okanagan) Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan) |
Peer Review Status | Unreviewed |
Scholarly Level | Undergraduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 52966-Hatton_Jeff_Convex_functions_2021.pdf [ 881.95kB ]
- Metadata
- JSON: 52966-1.0398276.json
- JSON-LD: 52966-1.0398276-ld.json
- RDF/XML (Pretty): 52966-1.0398276-rdf.xml
- RDF/JSON: 52966-1.0398276-rdf.json
- Turtle: 52966-1.0398276-turtle.txt
- N-Triples: 52966-1.0398276-rdf-ntriples.txt
- Original Record: 52966-1.0398276-source.json
- Full Text
- 52966-1.0398276-fulltext.txt
- Citation
- 52966-1.0398276.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.52966.1-0398276/manifest