CGAL homepage   ACG at TAU  
TAU Members   People   Projects  

Lower Envelopes of Planar Curves

[discovered gouging]

Abstract

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.

Links

Contact

Ron Wein http://www.cs.tau.ac.il/~wein wein@post.tau.ac.il
Dan Halperin http://www.math.tau.ac.il/~halperin halperin@post.tau.ac.il

[Projects Page] [Top]
Site is maintained by Efi Fogel. Last modified: January 18 2005.