Auraria campus
Alexander Semyonov’s MS in Applied Mathematics Project Presentation
Monday, December 7 · 12 pm–1:30 pm
at Student Commons 4017

Title: Algorithms for the Computation of Upper Envelopes Abstract: Given a family of real-valued functions, the upper envelope is the function whose value at a given point is the maximum attained by the functions in the family defined at that point. For a family of continuous, univariate functions, in which every pair of distinct functions intersects a finite number of times, the sequence of functions appearing on the upper envelope corresponds to a Davenport-Schinzel sequence. This report will investigate the relationship between upper envelopes and Davenport-Schinzel sequences and examine established bounds on the length of an upper envelope sequence. Two efficient algorithms are presented for the computation of the upper envelope of continuous, univariate, totally-defined functions. The first algorithm follows a simple divide-and-conquer scheme in which the family of functions is divided into two halves, the upper envelope of each half is computed recursively, and the resulting envelopes are merged to build the complete upper envelope. The second algorithm utilizes a stack-based approach, analogous to convex hull construction, to compute the upper envelope of a family of linear…
Source: cu-denver · updated automatically. Times are Denver time. Doors, prices and lineups change — the ticket link is the truth.