Personal tools
You are here: Home Projects Internal Projects Lower Envelopes of Planar Curves
« June 2017 »
June
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
252627282930
Log in


Forgot your password?
 

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

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

Contact

Ron Wein http://www.cs.tau.ac.il/~wein wein@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin halperin@post.tau.ac.il
Document Actions