Minkowski Sum Selection and Finding

Let

P

,

Q

 ⊆ ℝ

2

be two

n

-point multisets and

Ar

 ≥ 

b

be a set of

λ

inequalities on

x

and

y

, where

A

 ∈ ℝ

λ

×2

,

$r=[^x_y]$

, and

b

 ∈ ℝ

λ

. Define the

constrained Minkowski sum

(

P

 ⊕ 

Q

)

Ar

 ≥ 

b

as the multiset {(

p

 + 

q

) |

p

 ∈ 

P

,

q

 ∈ 

Q

,

A

(

p

 + 

q

) ≥ 

b

}. Given

P

,

Q

,

Ar

 ≥ 

b

, an objective function

f

:ℝ

2

→ℝ, and a positive integer

k

, the

Minkowski Sum Selection

problem is to find the

k

th

largest objective value among all objective values of points in (

P

 ⊕ 

Q

)

Ar

 ≥ 

b

. Given

P

,

Q

,

Ar

 ≥ 

b

, an objective function

f

:ℝ

2

→ℝ, and a real number

δ

, the

Minkowski Sum Finding

problem is to find a point (

x

*

,

y

*

) in (

P

 ⊕ 

Q

)

Ar

 ≥ 

b

such that |

f

(

x

*

,

y

*

) − 

δ

| 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

λ

= 1; (2)

O

(

n

log

2

n

) time deterministic algorithms and expected

O

(

n

log

n

) time randomized algorithms for any fixed

λ

> 1. For the

Minkowski Sum Finding

problem with linear objective functions or objective functions of the form

$f(x,y)=\frac{by}{ax}$

, we construct optimal

O

(

n

log

n

) time algorithms for any fixed

λ

 ≥ 1. As a byproduct, we obtain improved algorithms for the

Length-Constrained Sum Selection

problem and the

Density Finding

problem.