In some multi-objective optimization problems (such as that exemplified by the choosing of hotels based on the sizes of their pools and quality scores of their restaurants), we may have different kinds of constraints involving the variables instead of the desire to avoid points dominated by others. Suppose, for example, that we have a two-variable optimization problem where we have a set, C, of constraints of the form, 

y ≥ m_ix + b_i, 

for real numbers, mi and bi, for i = 1, 2,...,n. In such a case, we would like to restrict our attention to points that satisfy all the linear inequality constraints in C. One way to address this desire is to construct the upper envelope for C, which is a representation of the function, f(x), defined as 

where the (m_i, b_i) pairs are from the inequalities in C. Equivalently, the upper envelope is a representation of the part of the plane determined by the intersection of all the halfplanes determined by the inequalities in C. If we consider how this function behaves as x goes from −∞ to +∞, we note that each inequality in C can appear at most once during this process. Thus, we can represent f in terms of a set, S = {(a₁, b₁, i₁),(a₂, b₂, i₂),...,(a_k, b_k, i_k)}, such that each triple, (a_j , b_j , i_j ) in S, represents the fact that interval [a_j , b_j] is a maximal interval such that f(x) = m_ij x + b_ij . Describe an O(n log n)-time algorithm for computing such a representation, S, of the upper envelope of the linear inequalities in C.

Transcribed Image Text:

= max {m;x + b;}, 1