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.
@cite_2 gave the first general algorithm. Their rank-sequence algorithm'' determines a rank sequence @math according to the application domain. Specifically a rank sequence is an ordered sequence of @math ranks @math . The corresponding partition of @math is computed. Each @math is reduced to just those elements in on block of the partition. When the elements are points and the sets are hyperplanes that form a projective space, it can be computed with linear comparisons, for a suitable rank sequence. However, the rank-sequence algorithm is no better than the trivial algorithm above in the worst case. It was shown by @cite_1 that for some collection of subsets there are no good rank sequence for which the number of comparisons made by the algorithm is linear.
@cite_1 @cite_2
2413157087 783504
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.