Upper Envelope of Multidimensional Piecewise-Quadratic Functions

Question

I am trying to find the upper envelope to a set of piecewise-quadratic functions. The problem is easy enough to solve in the 1-dimensional case, as it amounts to finding and pruning the intersections of all functions.

This becomes much harder when the functions are multidimensional. Any hints to sources from computational geometry are greatly appreciated.

Answer 1

Here I respond concerning envelopes of surfaces in $\mathbb{R}^3$ (not necessarily higher dimensions).

One source (with references) is the CGAL manual, Envelopes of Surfaces in 3D.

---

           
            ^{CGAL figure.}

Their software doesn't explicitly handle quadratic surfaces, however (aside from spheres).

These twos papers, and their citations, may help:

Boissonnat, Jean-Daniel, and Katrin TG Dobrindt. "On-line construction of the upper envelope of triangles and surface patches in three dimensions." Computational Geometry 5.6 (1996): 303-320. Journal link.

Meyerovitch, Michal. "Robust, generic and efficient construction of envelopes of surfaces in three-dimensional spaces." ESA: European Symposium on Algorithms. 2006. Springer link. PDF download.

---

           
            ^{Meyerovitch figure.}

---