{"id":"arxiv/2609.19343","url":"https://arxiv.org/abs/2609.19343","tags":["math.OC","cs.SC"],"score":0,"title":"Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time","domain":"math.OC","source":"arxiv","authors":["Tanmaya Karmarkar","Yves Lucet"],"reviews":0,"subject":"math.OC","summary":"We compute the convex envelope of (nonconvex) bivariate piecewise linear-quadratic (PLQ) functions (bivariate quadratic functions defined on a polyhedral subdivision). Our algorithm is composed of the following steps: (1) compute the convex envelope of each quadratic piece obtaining piecewise rational functions (quadratic divided by linear function) defined over a polyhedral subdivision; (2) compute the (Legendre-Fenchel) conjugate of each resulting piece to obtain piecewise quadratic functions defined over a parabolic subdivision; (3) compute the maximum of all those functions to obtain the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}