Hitting or Avoiding Balls in Euclidean Space ^{∗}

Yves Crama^{†}  Toshihide Ibaraki^{‡}

May 10, 2000

Abstract. We investigate the algorithmic complexity of several geometric problems of the following type: given a “feasible” box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. We establish that all these problems are NP-hard in their most general version. We derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, we show that all these problems can be solved in polynomial time when the dimension of the space is fixed.

1 Introduction

In this paper, we consider various algorithmic problems of the following nature: given a “feasible” region Q and n balls B_{1}, B_{2}, …, B_{n} in Euclidean space R^{d}, find a feasible point which is covered by as few or, respectively, by as many balls as possible.

The maximization variant of this problem has been previously studied by several authors (e.g. [2, 4, 5, 8, 19], etc). The main motivation for considering this problem stems from a product positioning problem arising in marketing theory. In this framework, R^{d} is the space of attributes of a family of existing products, which are represented by points p_{1}, p_{2}, …, p_{m} in R^{d}. Customer groups are also represented by points c_{1}, c_{2}, …, c_{n} in R^{d}, each of which can be viewed as describing the attributes of the “ideal” product for this customer group. Each group is assumed to buy that product which is closest (in the Euclidean sense) to its representative point. The product positioning problem is now to locate a new product in a feasible region Q ⊆ R^{d} so as to maximize the market share captured by this new entry. Observe that, in view of our assumption regarding customer behavior, the new product p will be bought by customer group c_{i} if and only if p is contained in the ball B_{i} with center c_{i} and with radius min_{k=1,...,m} ∥c_{i} − p_{k}∥. Thus, in order to maximize its market share, the new product should be covered by as many as possible of the balls B_{1}, B_{2}, …, B_{n}. We refer for instance to the paper [8] or to the surveys by Green and Krieger [9] or Schmalensee and Thisse [18] for a more thorough discussion of the relevance of this model in the marketing context.

∗This research was supported in part by a Scientific Grant in Aid of the Ministry of Education, Science and Culture of Japan, by ONR grants N00014-92-J-1375 and N00014-92-4083, and by NATO grant CRG 931531.

†Ecole d’Administration des Affaires, Université de Liège, Bld du Rectorat 7 (B31), 4000 Liège, Belgium.

Email: crama@vm1.ulg.ac.be

‡Department of Applied Mathematics and Physics, Graduate School of Engineering, Kyoto University, Kyoto, Japan 606. Email: ibaraki@kuamp.kyoto-u.ac.jp

A variant of the above model arises if we assume that the customers are somehow “continuously distributed” over a region Q of R^{d} and that each product p_{i} is characterized by a “radius of attraction” r_{i}. Customer c buys product p_{i} if and only if c lies close enough to p_{i}, viz. if c lies in the ball with center p_{i} and with radius r_{i} (in this model, products are not assumed to be competing with each others, so that a customer may buy several of them). A point p ∈ Q that is not covered by any ball can be viewed as a segment of the customer population which does not buy any of the existing products, and which therefore constitutes an unexplored marketing “niche”. If no such uncovered point exists, then any minimally covered point similarly defines a region of the space where customer requirements may be unsufficiently met by existing products.

More generally, choice and preference models based on proximity considerations in perceptual or attribute spaces have been extensively considered in the mathematical psychology literature (see e.g. Coombs [3]). In this framework, points that are maximally, resp. minimally, covered can be naturally interpreted as representing choice alternatives that are selected by a maximal, resp. a minimal, number of individuals. This observation, together with the obvious symmetry between the maximizing and minimizing variants of our problems, provides the main motivation for the work described in this paper.

In the next section, we give a more precise definition of the problems to be investigated. In Section 3, we establish that all these problems are NP-hard in their most general version. In Section 4, we restrict our attention to the one-dimensional situation (i.e., d = 1), and we derive tight bounds on the complexity of the resulting problems. More generally, we show in Section 5 that all problems considered here can be solved in polynomial time when the dimension d of the space is fixed. Some of these results are further improved in Section 6.

2 Definitions and Statement of the Problems

Given n balls in Euclidean space R^{d}, either all closed,

B_{i} = {x ∈ R^{d} | ∥x − c_{i}∥ ≤ r_{i}} (i = 1, 2, …, n)

or all open,

B_{i} = {x ∈ R^{d} | ∥x − c_{i}∥ < r_{i}} (i = 1, 2, …, n),

where c_{i} ∈ R^{d} and r_{i} ∈ R (i = 1, 2, …, n), and given a closed box

Q = {x ∈ R^{d} | l_{j} ≤ x_{j} ≤ u_{j}, j = 1, 2, …, d},

we consider the following problems.

Feasibility: Decide if there is a point x ∈ Q \ (⋃_{i=1}^{n} B_{i}).

Mimimum covering: Find a point x ∈ Q that minimizes |{i = 1, 2, …, n | x ∈ B_{i}}|.

Maximum covering: Find a point x ∈ Q that maximizes |{i = 1, 2, …, n | x ∈ B_{i}}|.

When a statement about balls does not specify whether the balls are open or closed, it means that the statement holds in both cases. We denote by MIN-CLOSED (resp. MIN-OPEN) the version of minimum covering in which all balls are closed (resp. open). Similarly for MAX-CLOSED and MAX-OPEN.

3 NP-Hardness Results

All three problems defined in Section 2 turn out to be NP-hard in their full generality.

Theorem 1 The feasibility problem is NP-complete. Proof. The feasibility problem is in NP (this may not be entirely obvious at first, but follows for instance from Proposition 3 in Section 5).

We first consider the case where all balls are closed. Consider an instance of 3-SAT with clauses C_{1}, C_{2}, …, C_{n} over the set of boolean variables {x_{1}, x_{2}, …, x_{d}}, where each clause contains three literals (see e.g. Garey and Johnson [7]). With each clause C_{i} = x_{h} ∨ x_{k} ∨ x_{l}, we associate a closed ball

B_{i} = \{x ∈ R^{d} | x_{h}^{2} + x_{k}^{2} + x_{l}^{2} + ∑_{j≠h,k,l}(x_{j} − \frac{1}{2})^{2} ≤ \frac{d}{4} \},

for i = 1, 2, …, n. If a negated literal x̄_{h} appears in C_{i}, use (1 − x_{h})^{2} instead of x_{h}^{2} in the above definition. Then define the unit hypercube

Q = {x ∈ R^{d} | 0 ≤ x_{j} ≤ 1, j = 1, 2, …, d}.

We claim that clauses C_{1}, C_{2}, …, C_{n} are simultaneously satisfiable if and only if there exists a point x ∈ Q \ (⋃_{i=1}^{n} B_{i}). To see this, consider an arbitrary clause C_{i} = x_{h} ∨ x_{k} ∨ x_{l}. Notice that, for any x ∈ {0, 1}^{d}, x satisfies C_{i} if and only if x ∉ B_{i} (by definition of B_{i}). This trivially implies the “only if ” part of the claim. For the “if ” part, consider any point x ∈ Q \ B_{i}. Define another point y ∈ {0, 1}^{d} by

y_{j} = \{ \begin{matrix}0, & if x_{j} < 1/2 \\ 1, & if x_{j} ≥ 1/2. \end{matrix}

Since x ∉ B_{i}, we obtain successively

d/4 < x_{h}^{2} + x_{k}^{2} + x_{l}^{2} + ∑_{j≠h,k,l}(x_{j} − \frac{1}{2})^{2}
≤ x_{h}^{2} + x_{k}^{2} + x_{l}^{2} + (d − 3)/4,

thus x_{h}^{2} + x_{k}^{2} + x_{l}^{2} > 3/4, and one of x_{h}, x_{k}, x_{l} must be larger than 1/2. This implies in turn that one of y_{h}, y_{k}, y_{l} is equal to 1, and thus clause C_{i} is satisfied by y.

This shows that the feasibility problem for closed balls is NP-complete.

It is easy to see that a similar proof works when all balls B_{1}, B_{2}, …, B_{n} are open: it suffices to replace the radius d/4 by d/4 + ϵ, where 0 < ϵ ≤ 1/4. □

Theorem 2 MIN-CLOSED and MIN-OPEN are NP-hard. Proof. This is an immediate corollary of Theorem 1. □

Theorem 3 MAX-CLOSED and MAX-OPEN are NP-hard. Proof. First recall that MIN-SAT is the following problem: given an instance C_{1}, C_{2}, …, C_{n} of the satisfiability problem and an integer m, decide whether there exists a truth assignment such that at least m of the clauses C_{1}, C_{2}, …, C_{n} are not satisfied. It is known that MIN-SAT is NP-complete even when every clause contains at most 2 literals (we call MIN-2-SAT this restricted version of the problem; see [12]).

Now, given an instance of MIN-2-SAT with clauses C_{1}, C_{2}, …, C_{n} over the variables {x_{1}, x_{2}, …, x_{d}}, we construct an instance of MAX-CLOSED as follows. With each clause, for example C_{i} = x_{h} ∨ x̄_{k}, we associate a closed ball

B_{i} = \{x | (d + x_{h})^{2} + (d + 1 − x_{k})^{2} + ∑_{j≠h,k}(x_{j} − \frac{1}{2})^{2} ≤ 2d^{2} + d\}.

We claim that there is a point y ∈ {0, 1}^{d} that does not satisfy m of the clauses C_{1}, C_{2}, …, C_{n} if and only if there is a point x ∈ R^{d} that lies in m of the balls B_{1}, B_{2}, …, B_{n}.

Indeed, for any x ∈ {0, 1}^{d}, x does not satisfy C_{i} if and only if x ∈ B_{i}. This implies the “only if” part of the claim. Conversely, assume that x ∈ B_{i}, and assume for example that C_{i} = x_{h} ∨ x̄_{k}. If x_{h} ≥ 1/2 or x_{k} ≤ 1/2, then

(d + x_{h})^{2} + (d + 1 − x_{k})^{2} + ∑_{j≠h,k}(x_{j} − \frac{1}{2})^{2} ≥ (d + \frac{1}{2})^{2} + d^{2} > 2d^{2} + d,

contradicting x ∈ B_{i}. Thus x_{h} < 1/2 and x_{k} > 1/2. Define now a point y ∈ {0, 1}^{d} by

y_{j} = \{ \begin{matrix}0, & if x_{j} < 1/2 \\ 1, & if x_{j} ≥ 1/2. \end{matrix} .

Then, y does not satisfy C_{i}. Therefore, if there is a point x in B_{i_{1}} ∩ B_{i_{2}} ∩ ⋯ ∩ B_{i_{m}}, then the corresponding y does not satisfy any of C_{i_{1}}, C_{i_{2}}, …, C_{i_{m}}. This establishes the “if” part of the claim, and proves the NP-hardness of MAX-CLOSED.

It is easy to see that the above construction also works for MAX-OPEN. □

For closed balls, Theorem 3 was first proved in [4] by a more involved argument. As observed by a referee, Theorem 3 is also a close relative of the (folklore?) result according to which it is NP-hard to find a largest feasible subsytem of a system of linear inequalities.

4 Problems in One-Dimensional Space

We show in this section that when d = 1, i.e. the dimension of the Euclidean space is one, then all problems defined in Section 2 can be solved in O(n log n) time and this time bound is optimal.

Let us first state a lemma (we refer to Preparata and Shamos [16] for a definition of the algebraic decision tree computational model).

Lemma 1 The following problems require Ω(n log n) operations in the algebraic decision tree model:

(P1) Given (a_{1}, a_{2}, …, a_{n}) ∈ R^{n}, decide whether there exists a permutation π of {1, 2, …, n} such that

a_{π(i+1)} = a_{π(i)} + 1 (i = 1, 2, …, n − 1).

(P2) Given (a_{1}, a_{2}, …, a_{n}) ∈ R^{n}, decide whether there exists a permutation π of {1, 2, …, n} such that

a_{π(i)} ∈ (i − 1, i) (i = 1, 2, …, n),

where (i − 1, i) denotes the open interval with endpoints i − 1 and i. Proof. We apply a general result due to Ben-Or, as presented in Preparata and Shamos (Theorem 1.2 in [16]). Let S_{n} be the set of all permutations of {1, 2, …, n}. For π ∈ S_{n}, consider the lines in n-space

W_{π} = {x ∈ R^{n} | x_{π(i+1)} = x_{π(i)} + 1, i = 1, 2, …, n − 1}
V_{π} = {x ∈ R^{n} | x_{π(i)} ∈ (i − 1, i), i = 1, 2, …, n}.

Clearly, (a_{1}, a_{2}, …, a_{n}) is a Yes-instance of (P1) (resp. (P2)) if and only if (a_{1}, a_{2}, …, a_{n}) ∈ ⋃_{π∈S_{n}} W_{π} (resp. (a_{1}, a_{2}, …, a_{n}) ∈ ⋃_{π∈S_{n}} V_{π}). Moreover, if π_{1} ≠ π_{2}, then W_{π_{1}} ∩ W_{π_{2}} = ∅ and V_{π_{1}} ∩ V_{π_{2}} = ∅; thus, ⋃_{π∈S_{n}} W_{π} and ⋃_{π∈S_{n}} V_{π} each have n! connected components. Ben-Or’s theorem now implies that O(log n!) = O(n log n) operations are necessary to solve (P1) or (P2) in the algebraic decision tree model, thus proving the lemma. □

As pointed out by a referee, the Ω(n log n) lower bound for problem (P1) was previously established by Lee and Wu [14] and Ramanan [17]. Here, Lemma 1 allows us to derive the following results: Proposition 1 The feasibility problem for closed balls in R (i.e., for closed intervals) requires Ω(n log n) operations in the algebraic decision tree model. Proof. Given an instance (a_{1}, a_{2}, …, a_{n}) of (P1) (see Lemma 1), define the following instance of the feasibility problem:

B_{i} = [a_{i}, a_{i} + 1] (i = 1, 2, …, n)

and

Q = [a_{min}, a_{min} + n]

where a_{min} = min{a_{1}, a_{2}, …, a_{n}}. Note that B_{i} and Q can be defined in linear time. Then, (a_{1}, a_{2}, …, a_{n}) is a Yes-instance of (P1) if and only if Q \ (⋃_{i=1}^{n} B_{i}) = ∅. Therefore, the statement follows from Lemma 1. □

Proposition 2 The feasibility problem for open balls in R (i.e., for open intervals) requires Ω(n log n) operations in the algebraic decision tree model. Proof. Given an instance (a_{1}, a_{2}, …, a_{n}) of (P2), define (in linear time) the following instance of the feasibility problem, involving 2n + 1 open balls and a box:

B_{i} = (a_{i} − \frac{1}{2}, a_{i} + \frac{1}{2}) (i = 1, 2, …, n)
I_{j} = (j − \frac{1}{2}, j + \frac{1}{2}) (j = 0, 1, …, n)
Q = [0, n].

We claim that (a_{1}, a_{2}, …, a_{n}) is a Yes-instance of (P2) if and only if

Q \ ( ⋃_{i=1}^{n} B_{i} ∪ ⋃_{j=0}^{n} I_{j}) = ∅.

Indeed, for any x ∈ Q, there holds that x ∉ ⋃_{j=0}^{n} I_{j} if and only if x ∈ \{i− \frac{1}{2} | i = 1, 2, …, n\}. Therefore,

Q \ ( ⋃_{i=1}^{n} B_{i} ∪ ⋃_{j=0}^{n} I_{j}) = ∅

⟺ ∀i ∈ \{1, 2, …, n\}; ∃π(i) ∈ \{1, 2, …, n\}; i − \frac{1}{2} ∈ B_{π(i)}
⟺ ∀i ∈ {1, 2, …, n}; ∃π(i) ∈ {1, 2, …, n}; a_{π(i)} ∈ (i − 1, i).

In these implications, π must be a permutation, since each of the balls B_{1}, B_{2}, …, B_{n} can contain at most one point of the form i − \frac{1}{2}, for i = 1, 2, …, n. This establishes the claim, and hence the proposition (via Lemma 1). □

Theorem 4 Feasibility problems, minimum covering problems and maximum covering problems in one dimensional space R can all be solved in Θ(n log n) time (in the sense of algebraic operations). Proof. Each ball in R is given as either a closed interval [a_{i}, b_{i}] or an open interval (a_{i}, b_{i}) for i = 1, 2, …, n, and a box is given as a closed interval Q = [l, u]. First sort all a_{i} and b_{i} belonging to Q by nondecreasing value (this requires O(n log n) time). Then scan the sorted list of 2n numbers from smallest to largest (this requires O(n) time). All problems in the theorem statement can easily be solved if, in the course of this scanning procedure, we keep track of how many intervals cover the point being scanned.

The resulting time bound O(n log n) is optimal for feasibility problems by Propositions 1 and 2. It is also optimal for minimum covering problems since these include feasibility problems as special cases.

To see that the time bound is also optimal for maximum covering problems, associate an instance of MAX-CLOSED with each instance of MIN-OPEN by associating the closed intervals [l, a_{i}] and [b_{i}, u] with each open interval (a_{i}, b_{i}) of MIN-OPEN (if l > a_{i} or b_{i} > u holds, ignore the corresponding interval). It is easy to see that the optimal solutions of these two problem instances coincide. Therefore MAX-CLOSED requires Ω(n log n) time.

The case of MAX-OPEN is analogous. □

Remark 1 Problems (P1) and (P2) in Lemma 1 can be solved in O(n) time if the computational model is modified to allow the use of the floor function ⌊·⌋. For instance, when solving (P1), the floor function can be used to determine to which of the buckets

I_{i} = [a_{min} + i − 1, a_{min} + i) (i = 1, 2, …, n)

each a_{j} belongs. If some a_{j} does not fall in any of these buckets, then we are done. Thus, assume a_{j} ∈ I_{π(j)} for j = 1, 2, …, n. Check whether a_{j} = a_{min} + π(j) − 1 for each j, and check whether π is a permutation. If so, then answer “Yes”, otherwise answer “No”.

By contrast, however, we do not know whether the feasibility problem can be solved in O(n) time when the floor function is available. □

5 Power Diagrams and d-Dimensional Problems

We show in this section that our problems can be solved in polynomial time when d, i.e. the dimension of the space, is fixed. In order to achieve polynomiality, we make extensive use of the concept of power diagram, which allows us to tackle feasibility, minimum covering and maximum covering problems in a unifying framework.

Power diagrams generalize Voronoi diagrams and provide a rather standard tool for the investigation of computational geometry problems involving balls (see for instance Aurenhammer [1], Imai, Iri and Murota [11] – for the planar case –, Edelsbrunner [6], Preparata and Shamos [16]). However, their properties are not widely known in the Operations Research community, and their relevance to the class of problems considered in this paper seems to have gone unnoticed so far. Let us start, therefore, with some basic definitions.

The power of a point x ∈ R^{d} with respect to a ball B ⊆ R^{d} with center c ∈ R^{d} and radius r ∈ R is defined by

pow(x, B) =∥ x − c ∥^{2} −r^{2}.

(This quantity is sometimes called the Laguerre distance of the point to the ball). The following properties are immediate consequences of the definition:

pow(x, B) < 0 if x is in the interior of B,
pow(x, B) = 0 if x is on the boundary of B,
pow(x, B) > 0 otherwise.

Fix a collection B_{1}, B_{2}, …, B_{n} of balls in R^{d}. For j ∈ {1, 2, …, n}, define the power cell of B_{j} by

cell(B_{j}) = {x ∈ R^{d} | pow(x, B_{j}) ≤ pow(x, B_{i}) for all i ≠ j}.

The power diagram of B_{1}, B_{2}, …, B_{n}, denoted PD(B_{1}, B_{2}, …, B_{n}) (or PD for short), is the collection of all cells cell(B_{1}), cell(B_{2}), …, cell(B_{n}). For a given (closed) box Q ⊆ R^{n}, define

cell_{Q}(B_{j}) = cell(B_{j}) ∩ Q (j = 1, 2, …, n)

and

PD_{Q}(B_{1}, B_{2}, …, B_{n}) = {cell_{Q}(B_{j}) | j = 1, 2, …, n}.

It is known that each cell_{Q}(B_{j}) is a closed polyhedron. We denote by V_{j} the vertex-set of cell_{Q}(B_{j}), and we let

V = ⋃_{j=1}^{n} V_{j}.

The next result motivates our interest in power diagrams: it implies that, if an instance of the feasibility problem is a Yes-instance, then it has a solution among the vertices of the power diagram.

Proposition 3 The box Q is not covered by ⋃_{j=1}^{n} B_{j} (i.e., the answer to the feasibility problem is Yes) if and only if there exists i ∈ {1, 2, …, n} and a vertex v ∈ V_{i} such that v ∉ B_{i}. Proof. To show the “if” part, assume that v ∈ V_{i} \ B_{i} for some i. Since v ∈ cell_{Q}(B_{i}), pow(v, B_{i}) ≤ pow(v, B_{j}) for all j ≠ i. Together with v ∉ B_{i}, this implies that v ∉ B_{j} for all j, and thus v is not covered by ⋃_{j=1}^{n} B_{j}.

To show the converse, assume now that u ∈ Q \ ⋃_{j=1}^{n} B_{j}. For some i ∈ {1, 2, …, n}, we have u ∈ cell_{Q}(B_{i}). Let v be a point maximizing pow(x, B_{i}) over cell_{Q}(B_{i}). Since cell_{Q}(B_{i}) is a polyhedron and the power function is convex, we may assume that v ∈ V_{i}. Moreover, since u ∉ B_{i} and pow(v, B_{i}) ≥ pow(u, B_{i}), we see that v ∉ B_{i}, as required. □

Observe that Proposition 3 holds independently of whether the balls B_{1}, B_{2}, …, B_{n} are closed or open.

Consider now the following procedure for the feasibility problem.

PROCEDURE 1 (to solve the feasibility problem):

construct PD_{Q}(B_{1}, B_{2}, …, B_{n}) and V;

for each vertex v ∈ V do

begin find i ∈ {1, 2, …, n} such that v ∈ cell_{Q}(B_{i}); if v ∉ B_{i} then return “yes” {i.e., v ∈ Q \ ⋃_{j=1}^{n} B_{j}}

end; return “no”.

The correctness of this procedure is trivially implied by Proposition 3. Let us examine its complexity. Aurenhammer [1] shows that the power diagram PD can be computed in O(n log n) time when d = 2 (see also Imai, Iri and Murota [11]), in O(n^{⌈ \frac{d+1}{2} ⌉}) time when d ≥ 3, and in O(n^{⌊ \frac{d+1}{2} ⌋}) space for all d. PD is then represented by a data structure in which each face (of dimension 0, 1, …, d − 1) of the cells of PD corresponds to a node, and incident faces are associated via pointers. The coordinates of the vertices of V are also recorded. The number of vertices (i.e., faces of dimension 0) and edges (i.e., faces of dimension 1) of PD is O(n^{⌈ \frac{d}{2} ⌉}). It follows that PD_{Q} can also be constructed in time O(n^{⌈ \frac{d+1}{2} ⌉}), by computing the penetration points of all edges of PD into the box Q. In PROCEDURE 1, the block begin-end is executed O(n^{⌈ \frac{d}{2} ⌉}) times. By means of the above data structure, each execution requires constant time. Thus we have established the next theorem:

Theorem 5 In fixed dimension d, the feasibility problem can be solved in O(n log n) time if d = 2, and in O(n^{⌈ \frac{d+1}{2} ⌉}) time if d ≥ 3. □

In view of Theorem 4, the time bound O(n log n) for d = 2 is optimal.

We next explain how the ideas described above can be extended to minimum and maximum covering problems, thus leading to solution algorithms with time complexity O(n^{d+2}) and space complexity O(n^{d+1}) for these problems. For MAX-CLOSED and MIN-OPEN, more efficient algorithms will be described in the next section.

For every subset T ⊆ {1, 2, …, n}, we define

cell(T) = {x ∈ R^{d} | pow(x, B_{i}) ≤ pow(x, B_{j}) for all i ∈ T and j ∉ T }.

This is the set of points which are closer (with respect to the power function) to the balls in T than to those not in T. For k = 1, 2, …, n, the order-k power diagram of B_{1}, B_{2}, …, B_{n} (or k-PD for short) is the collection of all cells cell(T) such that |T | = k. The intersection of cell(T) with Q is denoted cell_{Q}(T), and the corresponding collection for |T | = k is denoted k-PD_{Q}. Similarly to the case of PD_{Q}, each cell_{Q}(T) is a polyhedron, whose vertex-set we denote by V_{T}. Finally, we let

V^{(k)} = ⋃_{|T |=k} V_{T} .

Based on these definitions, we can now establish that an optimal solution of the minimum covering problem is to be found among the vertices of 1-PD_{Q}, 2-PD_{Q}, …, n-PD_{Q}. More precisely:

Proposition 4 For k = 1, 2, …, n, the optimal value of the minimum covering problem is at most k −1 if and only if there exists v ∈ V^{(k)} such that |{i = 1, 2, …, n | v ∈ B_{i}}| ≤ k −1. Proof. The condition is clearly sufficient. In order to prove its necessity, let u be an optimal solution of the minimum covering problem, and assume without loss of generality that pow(u, B_{1}) ≤ pow(u, B_{2}) ≤ … ≤ pow(u, B_{n}) and that u ∉ B_{j} for all j ≥ k (this implies in particular that u ∈ cell_{Q}({1, …, k})). Let v be a maximizer of pow(x, B_{k}) over cell_{Q}({1, …, k}). By convexity of the power function, we can take v to be a vertex of cell_{Q}({1, …, k}). Moreover, since both u and v are in cell_{Q}({1, …, k}), there holds pow(u, B_{k}) ≤ pow(v, B_{k}) ≤ pow(v, B_{j}) for all j ≥ k. Since u ∉ B_{k}, we see that, for all j ≥ k, v ∉ B_{j}. Thus, v is in at most k − 1 of the balls B_{1}, B_{2}, …, B_{n}, as required. □

Proposition 4 suggests the following procedure:

PROCEDURE 2 (to solve MIN-OPEN and MIN-CLOSED):

construct 1-PD_{Q}, 2-PD_{Q}, …, n-PD_{Q};

for k = 1 to n and for each vertex v ∈ V^{(k)} do

begin find the set T = {i = 1, 2, …, n | v ∈ B_{i}}; if |T | < k then return v and k − 1 (i.e., v is optimal)

end.

Theorem 6 In fixed dimension d, minimum covering problems can be solved in O(n^{d+2}) time. Proof. It follows from Proposition 4 that PROCEDURE 2 correctly solves minimum covering problems.

As for its complexity, notice that the diagrams 1-PD_{Q}, 2-PD_{Q}, …, n-PD_{Q} together contain O(n^{d+1}) facets and O(n^{d+1}) vertices, and that constructing all these diagrams takes O(n^{d+1}) time and space (see [1]). Since the block begin-end of PROCEDURE 2 is executed O(n^{d+1}) times and each execution can be done in linear time by using appropriate data structure, the total time required by the procedure is O(n^{d+2}). □

Let us now turn to maximum covering problems. Our procedure for these problems is based on the following easy observation:

Proposition 5 If T is a maximal subset of {1, 2, …, n} such that Q ∩ (∩_{j∈T} B_{j}) ≠ ∅, then cell_{Q}(T) ≠ ∅. Proof. Assume first that B_{1}, B_{2}, …, B_{n} are all closed. Then, for every point v in Q ∩ (∩_{j∈T} B_{j}), there holds pow(v, B_{j}) ≤ 0 if j ∈ T, and pow(v, B_{j}) > 0 if j ∉ T (by maximality of T). Thus, v ∈ cell_{Q}(T). A similar argument applies, mutatis mutandis, when B_{1}, B_{2}, …, B_{n} are open. □

Proposition 5 implies that, when solving the maximum covering problem, we can restrict our attention to subsets of balls such that cell_{Q}(T) is nonempty. Therefore, the following algorithm is correct:

PROCEDURE 3 (to solve MAX-OPEN and MAX-CLOSED):

construct 1-PD_{Q}, 2-PD_{Q}, …, n-PD_{Q};

for k = n down to 1 and for all T ⊆ {1, 2, …, n} with |T | = k and cell_{Q}(T) ≠ ∅ do

begin if Q ∩ (∩_{j∈T} B_{j}) ≠ ∅ then return T (i.e., any point in Q ∩ (∩_{j∈T} B_{j}) is optimal)

end.

Theorem 7 In fixed dimension d, maximum covering problems can be solved in O(n^{d+2}) time. Proof. PROCEDURE 3 is clearly correct. Regarding its complexity, we notice that the only difficulty consists in testing efficiently whether Q ∩ (∩_{j∈T} B_{j}) ≠ ∅ for various sets T. So, consider any set T for which the test must be performed. We claim first that Q∩(∩_{j∈T} B_{j}) ≠ ∅ if and only if, for some i ∈ T, cell_{Q}(T \ {i}) ∩ B_{i} ≠ ∅.

Indeed, let v ∈ Q ∩ (∩_{j∈T} B_{j}). We can freely assume that T is maximal with the property that Q ∩ (∩_{j∈T} B_{j}) ≠ ∅, for otherwise PROCEDURE 3 would have terminated earlier. Thus, as in the proof of Proposition 5, v ∈ cell_{Q}(T). Now, if i ∈ T is chosen such that pow(v, B_{i}) ≥ pow(v, B_{j}) for all j ∈ T, we obtain that v ∈ cell_{Q}(T \ {i}) ∩ B_{i}.

Conversely, if v ∈ cell_{Q}(T \ {i}), then pow(v, B_{i}) ≥ pow(v, B_{j}) for all j ∈ T, and hence v ∈ B_{i} implies v ∈ Q ∩ (∩_{j∈T} B_{j}).

Having thus proved the claim, we deduce that each test of the form “Is Q ∩ (∩_{j∈T} B_{j}) empty?” can be reduced to a sequence of |T | tests (corresponding to all i ∈ T) of the form: “Is cell_{Q}(T \ {i}) ∩ B_{i} empty?”.

Each of the latter subproblems can in turn be formulated as a convex quadratic minimization problem with linear constraints: in this formulation, the objective is to find a point v which minimizes the quantity pow(v, B_{i}), and the constraints on v correspond to the facets of cell_{Q}(T \ {i}) (i.e., faces of cell_{Q}(T \ {i}) whose dimension is the dimension of the cell minus 1). For fixed d, this minimization subproblem can be solved in time linear in the number of constraints (see Megiddo [15]).

It can be verified that, over the complete execution of PROCEDURE 3, each facet of 1-PD_{Q}, 2-PD_{Q}, …, n-PD_{Q} appears as a constraint in O(n) minimization subproblems. Indeed, consider any facet F, and assume that F is the intersection of two cells cell_{Q}(T_{1}) and cell_{Q}(T_{2}). Then, F gives rise to a constraint in each of the (n − |T_{1}|) tests associated with sets T of the form T = T_{1} ∪ {i}, for i ∈ {1, 2, …, n} \ T_{1}. And similarly, F gives rise to a constraint in each of the (n − |T_{2}|) tests associated with sets T of the form T = T_{2} ∪ {i}, for i ∈ {1, 2, …, n} \ T_{2}. Thus, in total, F generates (2n − |T_{1}| − |T_{2}|) constraints over the whole procedure.

Since there are O(n^{d+1}) facets in 1-PD, 2-PD, …, n-PD, and since each convex quadratic subproblem can be solved in time linear in the number of constraints (i.e., facets) in its formulation, we conclude that the time complexity of PROCEDURE 3 is O(n^{d+2}). □

6 Faster Algorithms for MAX-CLOSED and MIN-OPEN

In this section, we revisit the problems MAX-CLOSED and MIN-OPEN in fixed dimension d, and propose more efficient algorithms than those presented in Section 5. These two problems share the property that an optimal solution can always be found on the boundary of some subset of balls. As we shall see, this property makes them slightly easier to solve than their respective counterparts, MAX-OPEN and MIN- CLOSED.

Drezner [5] proposed an O(n^{2} log n) time algorithm for MAX- CLOSED in R^{2}, and Crama, Hansen and Jaumard [4] extended his approach to derive an O(n^{d+1}) time algorithm for MAX-CLOSED in R^{d}. In this section, we improve the latter to O(n^{d} log n) time. (Notice that [5, 4] do not consider a feasible box Q, as we do here.) We now briefly describe the ideas behind these algorithms, since they will be the starting point for the algorithms to be presented below. Throughout this section, we denote by Ṡ the boundary of a set S ⊆ R^{d}.

Drezner [5] first shows that, if the optimum value of MAX-CLOSED in R^{2} is at least 2, then some optimal solution lies at the intersection of two circles. By successively considering each of the n circles, this allows him to reduce the solution of MAX-CLOSED in R^{2} to the solution of the following n subproblems (SPk), for k = 1, 2, …, n:

(SPk) Given n closed balls B_{1}, B_{2}, …, B_{n} ⊆ R^{2}, find a point x ∈ Ḃ_{k} that maximizes

f_{k}(x) = |{i ∈ {1, 2, …, n} \ {k} | x ∈ B_{i}}|.

Problem (SPk) can best be seen as a 1-dimensional maximum covering problem, since its feasible set is restricted to the boundary of B_{k}. Therefore, it should be no surprise that (SPk) can be solved in O(n log n) time by a straightforward adaptation of the algorithm outlined in the proof of Theorem 4. More specifically, Drezner solves (SPk) as follows. Let a_{i}, b_{i} be the intersection points of Ḃ_{i} with Ḃ_{k} for i ≠ k. Sort I_{k} = ⋃_{i≠k}{a_{i}, b_{i}} according to the order in which these points are encountered when moving along Ḃ_{k} starting from an arbitrary point p ∈ Ḃ_{k} (this step requires O(n log n) time). Compute f_{k}(x) for all x ∈ I_{k}, starting from f_{k}(p) and updating the value of f_{k} according to whether each point of I_{k} corresponds to an “entry” point into some ball B_{i} or an “exit” point from B_{i} (this step takes O(n) time). In this way, a maximizer of f_{k} over I_{k} (i.e., an optimal solution of (SPk)) can be computed in O(n log n) time.

In order to generalize Drezner’s approach, Crama, Hansen and Jaumard [4] defined the concept of representative set of points. We next introduce a variant of this concept which will lead to more efficient algorithms. First, denote by Ḃ_{n+1}, Ḃ_{n+2}, …, Ḃ_{n+2d} the hyperplanes {x ∈ R^{d} | x_{j} = l_{j}} and {x ∈ R^{d} | x_{j} = u_{j}} (j = 1, 2, …, n) defining the facets of Q. Also, for any set F ⊆ {1, 2, …, n + 2d}, denote by L(F) the smallest linear subspace containing (some translate of ) ∩_{i∈F} Ḃ_{i}. Now, a set P ⊆ R^{d} (d ≥ 3) is called max-representative for Ḃ_{1}, Ḃ_{2}, …, Ḃ_{n+2d} if, for all F ⊆ {1, 2, …, n + 2d} such that 1 ≤ |F | ≤ d − 1,

(i ) if |F | ≤ d − 2 and ∩_{i∈F} Ḃ_{i} ≠ ∅, then P contains at least one point of ∩_{i∈F} Ḃ_{i}; (ii ) if |F | = d − 1, ∩_{i∈F} Ḃ_{i} ≠ ∅ and dimL(F) ≤ 2, then P contains an optimal solution

of MAX-CLOSED restricted to solutions in ∩_{i∈F} Ḃ_{i}.

The following property generalizes Drezner’s result mentioned above (it is similar to Theorem 5 in [4]):

Lemma 2 If P is a max-representative set for Ḃ_{1}, Ḃ_{2}, …, Ḃ_{n+2d}, then P contains an optimal solution of MAX-CLOSED.

Proof. Let H be a maximum cardinality subset of {1, 2, …, n} such that Q∩(∩_{i∈H}B_{i}) ≠ ∅. Select an index set F ⊆ H ∪ {n + 1, n + 2, …, n + 2d}, as large as possible with the property that Q ∩ (∩_{i∈F} Ḃ_{i}) ∩ (∩_{i∈H\F} B_{i}) ≠ ∅. We consider three cases.

Case 1: |F | ≤ d − 2. Then, by definition of max-representative sets, P contains a point u ∈ ∩_{i∈F} Ḃ_{i}. We claim that u ∈ Q ∩ (∩_{i∈H}B_{i}), which implies that u is optimal for MAX-CLOSED. To verify the claim, observe first that the set ∩_{i∈F} Ḃ_{i} is connected (this follows from our assumption that |F | ≤ d − 2, together with the fact that all sets Ḃ_{i}, i ∈ F, are either spheres or hyperplanes). Hence, ∩_{i∈F} Ḃ_{i} contains a path from x to u, where x is any point in Q ∩ (∩_{i∈F} Ḃ_{i}) ∩ (∩_{i∈H\F} B_{i}). If the claim is false, then, when moving from x to u along this path, we must encounter a first boundary set Ḃ_{j}, for some index j ∉ F.

But this contradicts the choice of F, since F′ = F ∪ {j} is larger than F and satisfies Q ∩ (∩_{i∈F′} Ḃ_{i}) ∩ (∩_{i∈H\F′}B_{i}) ≠ ∅.

Case 2: |F | ≥ d−1 and dimL(F) > 2. In this case, it is easy to see that ∩_{i∈F} Ḃ_{i} = ∩_{i∈G}Ḃ_{i} for some set G ⊂ F such that |G| ≤ d − 2. Thus, P contains a point u ∈ ∩_{i∈F} Ḃ_{i}, and u can be shown to be optimal for MAX-CLOSED by the same argument as in Case 1 (observe that ∩_{i∈F} Ḃ_{i} is connected, since dimL(F) > 2).

Case 3: |F | ≥ d − 1 and dimL(F) ≤ 2. In this case, let G be any subset of F such that |G| = d − 1. Since P is max-representative, P contains an optimal solution of MAX-CLOSED restricted to ∩_{i∈G}Ḃ_{i}. By choice of H and G, this solution is also optimal for the unrestricted problem. □

In [4], a result similar to Lemma 2 leads to an O(n^{d+1}) time algorithm for MAX-CLOSED. We now show that an O(n^{d} log n) time procedure can be obtained if we combine Lemma 2 with Drezner’s O(n log n) algorithm for (SPk).

Consider the following procedure:

PROCEDURE 4 (to solve MAX-CLOSED):

P ← ∅;

for all F ⊆ {1, 2, …, n + 2d} such that |F | ≤ d − 2 and ∩_{i∈F} Ḃ_{i} ≠ ∅ do

begin find x ∈ ∩_{i∈F} Ḃ_{i}; P ← P ∪ {x}; f(x) ← |{i ∈ {1, 2, …, n} | x ∈ B_{i}}|

end; for all F ⊆ {1, 2, …, n + 2d} such that |F | = d − 1 and ∩_{i∈F} Ḃ_{i} ≠ ∅ do

begin compute the smallest linear subspace L(F) containing ∩_{i∈F} Ḃ_{i}; if dimL(F) > 2 then consider the next F else do begin {solve MAX-CLOSED over ∩_{i∈F} Ḃ_{i}}

Ḋ_{0} ← ∩_{i∈F} Ḃ_{i};

for all j ∈ {1, 2, …, n} \ F do D_{j} ← B_{j} ∩ L;

find x ∈ Q ∩ Ḋ_{0} which maximizes |{j ∈ {1, 2, …, n} \ F | x ∈ D_{j}}|; P ← P ∪ {x}; f(x) ← |{j ∈ {1, 2, …, n} \ F | x ∈ D_{j}}| + d − 1

end end;

return a maximizer of f over P.

We now have the announced result:

Theorem 8 In fixed dimension d, MAX-CLOSED can be solved in O(n^{d} log n) time.

Proof. To prove that PROCEDURE 4 is correct, we only need to show that the set P constructed by the procedure is max-representative. First, observe that P contains a point of ∩_{i∈F} Ḃ_{i} whenever |F | ≤ d − 2. On the other hand, if |F | = d − 1 and dimL ≤ 2, then the procedure computes an optimal solution of MAX-CLOSED under the additional restriction that this solution should be in Ḋ_{0} = ∩_{i∈F} Ḃ_{i}. Hence, the set P is max-representative.

Let us now analyze the complexity of PROCEDURE 4. The first “for all” loop requires O(n^{d−1}) times (there are O(n^{d−2}) subsets F of cardinality at most d − 2, and each execution of the “begin-end” block requires O(n) time). In the second “for all” loop, computing L, Ḋ_{0} and D_{i} (i ∈ {1, 2, …, n} \ F) only involves some linear algebra in d-dimensional space (see [4] for details). Since d is fixed, this requires constant time for each F.

The innermost “begin-end” block consists in solving MAX-CLOSED over Q∩Ḋ_{0}, where Ḋ_{0} is a circle (i.e., a sphere in L). This is a slight generalization of the subproblem (SPk) introduced earlier, in which the feasible box Q must now be taken into account. This problem is easily solved in O(n log n) time by a straightforward modification of Drezner’s procedure. Since there are O(n^{d−1}) sets F satisfying |F | ≤ d−1, the overall complexity of PROCEDURE 4 is O(n^{d} log n). □

We finally turn our attention to MIN-OPEN. Let us define a min-representative set analogously as a max-representative set, with the only difference that “MAX-CLOSED” should be replaced by “MIN-OPEN” in condition (ii ). Then, we can prove:

Lemma 3 If P is a min-representative set for Ḃ_{1}, Ḃ_{2}, …, Ḃ_{n+2d}, then P contains an optimal solution of MIN-OPEN.

Proof. Let x be an optimal solution of MIN-OPEN, let H = { i ∈ {1, 2, …, n} | x ∈ B_{i}}, and let F = { i ∈ {1, 2, …, n + 2d} | x ∈ Ḃ_{i}} (observe that H ∩ F = ∅, since all balls are open). We assume that x has been chosen (among all optimal solutions of MIN-OPEN) so that |F | is as large as possible. Now, we distinguish between three cases.

Case 1: |F | ≤ d − 2. Then, by definition of P, there exists a point u in P ∩ (∩_{i∈F} Ḃ_{i}). We claim that u ∈ Q and that, for all i ∈ {1, 2, …, n} \ H, u ∉ B_{i} (this implies in particular that u is optimal for MIN-OPEN, as required). Indeed, since |F | ≤ d − 2, the set ∩_{i∈F} Ḃ_{i} is connected. Hence, there is a path from x to u in ∩_{i∈F} Ḃ_{i}. If the claim is not valid, then, when moving from x to u along this path, we must encounter a first boundary set Ḃ_{j}, for some index j ∈ {1, 2, …, n + 2d} \ F. Let v be the intersection point of the path with Ḃ_{j}. If j ∈ H, then this means that v is a first point outside of ∩_{i∈H}B_{i} on the path, contradicting the optimality of x (v is in fewer balls than x). Thus, j ∉ H and v is optimal for MIN-OPEN (v is in the same balls as x). But now, this contradicts the choice of x, since F′ = F ∪ {j} is larger than F and F′ ⊆ { i ∈ {1, 2, …, n + 2d} | v ∈ Ḃ_{i}}.

Case 2: |F | ≥ d − 1 and dimL(F) > 2. Then, there exists a subset G of F such that |G| ≤ d − 2 and ∩_{i∈F} Ḃ_{i} = ∩_{i∈G}Ḃ_{i}, and we conclude as in Case 1.

Case 3: |F | ≥ d − 1 and dimL(F) ≤ 2. In this case, let G be any subset of F such that |G| = d − 1. Since P is min-representative, P contains an optimal solution (say u) of MIN-OPEN restricted to ∩_{i∈G}Ḃ_{i}. Since x ∈ ∩_{i∈G}Ḃ_{i}, u must also be optimal for the unrestricted problem. □

Based on Lemma 3, we obtain the following statement:

Theorem 9 In fixed dimension d, MIN-OPEN can be solved in O(n^{d} log n) time.

Proof. A straightforward adaptation of PROCEDURE 4, in which all “max” operators are replaced by “min” operators, yields the result. □

7 Discussion

The work described in this paper could be extended in several directions. First, weighted versions of the minimum and maximum covering problems are of immediate interest for the marketing applications discussed in the Introduction (see [18]). The reader will easily convince himself that, since all our algorithms are of enumerative type, they can easily be modified to handle weighted instances, without increase in computational complexity.

Next, one may also want to consider more general feasible regions than a box, as we have done it here. In particular, the case where Q is an arbitrary polyhedron seems quite natural. Here again, our algorithms could be modified to handle this broader class of instances, but their running time may now be affected by the “complexity” of the description of Q itself (e.g., by its number of facets).

Finally, interesting variants of our problems arise when the Euclidean space is replaced by other normed spaces. The case of the L_{∞}-norm has been considered by several authors (see e.g. [4, 10, 13]), but not much seems to be known, for instance, concerning the L_{1}-norm. Another variant consists in substituting the balls by ellipsoids. The maximum covering problem for ellipsoids has been much studied in connection with the product positioning problem; see e.g. [2, 8, 18, 19]. But here also, much work remains to be done.

Acknowledgments. The authors are grateful to Naoki Katoh of Kobe University of Commerce for pointing out the relevance of power diagrams in connection with the problems investigated here, and to two anonymous referees for useful comments on a first version of this paper.

References

[1] F. Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing 16 (1987) 78-96.

[2] S. Albers and K. Brockhoff, A procedure for new product positioning in an attribute space, European Journal of Operational Research 1 (1977) 230-238.

[3] C.H. Coombs, A Theory of Data, Wiley, New York, 1964.

[4] Y. Crama, P. Hansen and B. Jaumard, Complexity of product positioning and ball intersection problems, Mathematics of Operations Research 20 (1995) 885-894.

[5] Z. Drezner, On a modified one-center model, Management Science 27 (1981) 848-851.

[6] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1987.

[7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, New York, 1979.

[8] B. Gavish, D. Horsky and K. Srikanth, An approach to the optimal positioning of a new product, Management Science 29 (1983) 1277-1297.

[9] P.E. Green and A.M. Krieger, Recent contributions to optimal product positioning and buyer segmentation, European Journal of Operational Research 41 (1989) 127-141.

[10] H. Imai and T. Asano, Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane, Journal of Algorithms 4 (1983) 310-323.

[11] H. Imai, M. Iri and K. Murota, Voronoi diagram in the Laguerre geometry and its applications, SIAM Journal on Computing 14 (1985) 93-105.

[12] R. Kohli, R. Krishnamurti and P. Mirchandani, The minimum satisfiability problem, SIAM Journal on Discrete Mathematics 7 (1994) 275-283.

[13] D.T. Lee, Maximum clique problem of rectangle graphs, in Advances in Computing Research, Vol. 1 (F. Preparata, ed.), JAI Press Inc., Greenwich, CT, 1983, pp. 91-107.

[14] D.T. Lee and Y.F. Wu, Geometric complexity of some location problems, Algorithmica 1 (1986) 193-211.

[15] N. Megiddo, Linear programming in linear time when the dimension is fixed, Journal of the ACM 31 (1984) 114-127.

[16] F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985.

[17] P. Ramanan, Obtaining lower bounds using artificial components, Information Processing Letters 24 (1987) 243-246.

[18] R. Schmalensee and J.-F. Thisse, Perceptual maps and the optimal location of new products: an integrative essay, International Journal of Research in Marketing 5 (1988) 225-249.

[19] F.S. Zufryden, ZIPMAP - A zero-one integer programming model for market segmentation and product positioning, Journal of the Operational Research Society 30 (1979) 63-70.