Lower envelope are a basic structure in Computational Geometry. I will give some background on lower envelopes in three dimensions and describe in detail the divide-and-conquer algorithm, which we implemented. I will also describe our CGAL implementation design and some efficiency issues.
(This talk last 45min and addresses mostly geometry people)