Lower Envelopes of Planar Curves

Given a set of planar curves, which can be broken into x-monotone pieces and viewed as a set of functions \(c_1(x),\ldots, c_n(x)\), their lower envelope (upper envelope) is the pointwise minimum (maximum) of this set of functions. We have implemented an extension to the arrangement package of CGAL that handles the computation of the lower (or the upper) envelope of a set of planar curves. As in the arrangement package, we separate the topological structure of the envelope, represented as a minimization diagram, from its geomtery, thus we allow users to work with practically any family of planar curves. Users only need to supply a small set of operation for the family of curves using a traits class, which is identical to the arrangement traits class. In our implementation we take care of degenerate situations in order to insure the stability of the algorithm.