Personal tools
You are here: Home Projects Internal Projects Lower Envelopes of Planar Curves
« March 2017 »
Log in

Forgot your password?

Lower Envelopes of Planar Curves

[discovered gouging]


Given a set of planar curves, which can be broken into x-monotone pieces and viewed as a set of functions c1(x), ..., cn(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.


  • Dan Halperin, and Ron Wein
    Generic Implementation of the Construction of Lower Envelopes of Planar Curves
    Technical report, ECG-TR-361100-01 [link] [bibtex]


Ron Wein
Dan Halperin
Document Actions