maxima sets life is full of trade-offs we often have to trade off desired performance measure against corresponding cost supposefor the sake of an examplewe are interested in maintaining database rating automobiles by their maximum speeds and their cost we would like to allow someone with certain amount of money to query our database to find the fastest car they can possibly afford we can model such trade-off problem as this by using key-value pair to model the two parameters that we are trading offwhich in this case would be the pair (costspeedfor each car notice that some cars are strictly better than other cars using this measure for examplea car with cost-speed pair ( is strictly better than car with cost-speed pair ( at the same timethere are some cars that are not strictly dominated by another car for examplea car with cost-speed pair ( may be better or worse than car with cost-speed pair ( )depending on how much money we have to spend (see figure performance cost figure illustrating the cost-performance trade-off with pairs represented by points in the plane notice that point is strictly better than points cdand ebut may be better or worse than points abf gand hdepending on the price we are willing to pay thusif we were to add to our setwe could remove the points cdand ebut not the others formallywe say cost-performance pair (abdominates pair (cd(abif dthat isif the first pair has no greater cost and at least as good performance pair (abis called maximum pair if it is not dominated by any other pair we are interested in maintaining the set of maxima of collection of cost-performance pairs that iswe would like to add new pairs to this collection (for examplewhen new car is introduced)and to query this collection for given dollar amountdto find the fastest car that costs no more than dollars