MINKOWSKI SUM SELECTION AND FINDING
Let P, Q subset of R(2) be two n-point multisets and Ar >= b be a set of lambda inequalities on x and y,where A is an element of R(lambda x2), r = [(y)(x)], and b is an element of R(lambda). Define the constrained Minkowski sum (P circle plus Q)(Ar >= b) as the multiset {(p + q)vertical bar p is an element of P, q is an element of Q, A(p + q) >= b}.Given P, Q, Ar >= b, an objective function f : R(2) -> R, and a positive integer k, the MINKOWSKI SUM SELECTION problem is to find the kth largest objective value among all objective values of points in (P circle plus Q)(Ar >= b). Given P, Q, Ar >= b, an objective function f : R(2) -> R, and a real number delta, the MINKOWSKI SUM FINDING problem is to find a point (x*, y*) in (P circle plus Q)(Ar >= b) such that vertical bar f(x*, y*) - delta vertical bar is minimized. For the MINKOWSKI SUM SELECTION problem with linear objective functions, we obtain the following results: (1) optimal O(n log n)-time algorithms for lambda = 1; (2) O(n log(2) n)-time deterministic algorithms and expected O(n log n)-time randomized algorithms for any fixed lambda > 1. For the MINKOWSKI SUM FINDING problem with linear objective functions or objective functions of the form f(x, y) = by/ax, we construct optimal O(n log n)-time algorithms for any fixed lambda >= 1. As a byproduct, we obtain improved algorithms for the Length-Constrained Sum SELECTION problem and the Density Finding problem.
minkowski sum bioinformatics sequence analysis