In this paper we look at the classical set-maxima problem. We give a new result using a sparse lattice of subsets. We then extend this to a geometric setting. Let @math be a set of @math points in a plane and @math be a set of convex regions. Let a key value be assigned to each point. The problems is to determine for each convex region of @math the point having the largest key. We give a parameterized result for the comparison complexity.
Sorting problems have long been one of the foundations of theoretical computer science. Sorting problems attempt to learn properties of an unknown total order of a known set. We test the order by comparing pairs of elements, and through repeated tests deduce some order structure on the set. The set-maxima problem is: given a family S of subsets of a set X, produce the maximal element of each element of S. Local sorting is a sub-problem of set-maxima, when S is a subset of (X (choose) 2), i.e. there exists a graph G with vertex set X and edge set S. We compare algorithms by estimating the number of comparisons needed, as a function of n = |X|, and m = |S|. In this paper, we review the information-theory lower bounds for the set-maxima and local-sorting problems. We review deterministic algorithms which have optimally solved the set-maxima problem, as a function of m,n, in settings where extra assumptions about S have been made. Also, we review randomized algorithms for local sorting and set-maxima which achieve an optimal expected number of comparisons. The set maxima problem is as follows: given a family of subsets @math of a totally ordered set @math , find the maximum in each subset. The computational model is the comparison tree. One possible solution is to sort the set X, which requires @math comparisons. The open question is whether set maxima is easier than sorting.Here, a solution is presented that requires a linear number of comparisons for the following two cases: • The sets are hyperplanes in a d-dimensional projective geometry @math . In particular, the interesting case is @math , when the intersection of any two subsets is exactly one. • The sets are chosen randomly with probability @math for each element to be in a set. The random choices are mutually independent and the number of comparisons needed is linear with probability approaching 1 asymptotically.