Linear Time Algorithms for Euclidean 1-Center in $\mathfrak {R}^d$ with Non-linear Convex Constraints

Abstract

In this paper, we first present a linear-time algorithm to find the smallest circle enclosing n given points in $\mathfrak {R}^2$ with the constraint that the center of the smallest enclosing circle lies inside a given disk. We extend this result to $\mathfrak {R}^3$ by computing constrained smallest enclosing sphere centered on a given sphere. We generalize the result for the case of points in $\mathfrak {R}^d$ where center of the minimum enclosing ball lies inside a given ball. We show that similar problem of minimum intersecting/stabbing ball for set of hyper planes in $\mathfrak {R}^d$ can also be solved using similar techniques. We also show how minimum intersecting disk with center constrained on a given disk can be computed to intersect a set of convex polygons. Lastly, we show that this technique is applicable when the center of minimum enclosing/intersecting ball lies in a convex region bounded by constant number of non-linear constraints with computability assumptions. We solve each of these problems in linear time complexity for fixed dimension.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A classical facility location problem deals with a given set $\mathcal {P}$ of n points in the plane representing n customers. It is required to find the optimal location $c^*$ where a facility should be placed so as to minimize the Euclidean distance from $c^*$ to its farthest customer. Geometrically, this problem is equivalent to finding the smallest circle that encloses the given set of n points where $c^*$ is the center of this circle. This problem is called minimum enclosing circle or Euclidean 1-center problem. For geometric objects other than points in $\mathfrak {R}^d$ the facility location problem is called minimum stabbing ball or minimum intersecting ball. Originally, 1-center problem was posed by Sylvester [17] in 1857. Shamos [14], Shamos and Hoey [15] and Preparata [12] gave $O (n \log n)$ time algorithms to solve this problem.

Megiddo [10, 11] settled the problem in $\mathfrak {R}^d$ by giving an optimal O(n) algorithm. Hurtado et al. [7] extended Megiddo’s work to find 1-center constrained inside a convex m-gon in $\theta (n + m)$-time. Bose and Toussaint [2] proposed an $O((n + m) log(n + m) + k)$-time algorithm for the 1-center that lies inside a simple m-gon. Bose and Wang [3] removed the dependency on k from the running time. Roy et al. [13] addressed a query version of the problem, giving an algorithm that required $O(n \log n)$-time preprocessing on $\mathcal {P}$. Barba et al. [1] solved the problem when $\mathcal {P}$ is the set of vertices of a convex n-gon and the 1-center is constrained to lie within an m-gon in expected $\theta (n + m)$ time.

Sharir and Welzl [16] formulated a framework for LP-type problems to solve a class of optimization problems using randomization techniques. Matousek et al. gave a randomized algorithm to solve a general LP-type problem in expected linear time [9]. Chazelle and Matousek [4] showed whenever the LP-type problem satisfies some additional computational constraints then a linear deterministic algorithm can be devised using derandomization techniques on Clarkson’s linear time LPP solution [5]. The problem posed in this paper can be transformed to an LP-type problem with some extra constraints. To our knowledge, no one has attempted the class of LP-type problem with such constraints. The specialty of this paper is that we present a linear-time geometric algorithm to compute the 1-center with constant number of additional non-linear convex constraints of certain type.

In this paper we look at constrained version of minimum enclosing circle, sphere and balls, where the center lies inside a given circle, sphere and ball, respectively. We also solve the constrained version of minimum intersecting balls for hyperplanes in $\mathfrak {R}^d$ and for convex polygons in $\mathfrak {R}^2$. In plane, we even compute the constrained minimum intersecting disk when the intersected objects are convex polygons. We also show how our result can be generalized for O(1) number of other types of constraints. These constraints are of the type $f_i(x) \le 0$, where $x\in \mathfrak {R}^d$ is the 1-center, $f_i$’s are convex functions with computability assumptions as defined in Sect. 4. None of these problems have been addressed in the literature. We solve all these problem in linear time for fixed dimension d.

The organization of paper is as follows. In Sect. 2, we provide a linear time algorithm to find the Euclidean 1-center in $\mathfrak {R}^2$ which is constrained to lie on a given disk. In Sect. 3, we present an O(n) time algorithm to find the Euclidean 1-center in $\mathfrak {R}^3$ constrained to lie within a given ball. We discuss the generalization to $\mathfrak {R}^d$ and to other geometric objects in Sect. 4.

2 Minimum Enclosing Circle with Center Inside the Given Disk in Plane

Let $\mathcal {P}$ be set of n points in plane, $\mathcal {P} = \{p_1, p_2, \dots , p_n\}$. Let D be the given disk in the plane such that the Euclidean 1-center, denoted by $c_D$, is constrained to lie inside it. We solve the following problem.

Problem 1. Compute Euclidean 1-center $c_D$ of $\mathcal {P}$ such that $c_D \in D$. That is solve the following optimization problem for c:

$$\begin{aligned} {\min \nolimits _{c \in D} \max \nolimits _{1 \le i \le n} || c - p_i||} \end{aligned}$$

We solve this problem using prune and search technique. In every iteration we reduce the size of $\mathcal {P}$ by a fraction. First we solve the problem of computing Euclidean 1-center, denoted by $c_L$, constrained on the given line segment L using the techniques in [7, 10]. We summarize below the result that we use.

Lemma 1

Euclidean 1-center $c_L$ of $\mathcal {P}$ constrained on any given line segment L can be computed in O(n) time.

In the algorithms that we present, we need to compute extreme points, that is, points of $\mathcal {P}$ that are farthest from a given point $x \in \mathfrak {R}^2$. We denote these extreme points by $\mathcal {P}_x$.

Now, we present an algorithm to compute $c_D$. First, given a line $\ell$, we give a method to find the location of $c_D$ with respect to $\ell$. Let $C_p(c)$ be the circle centered at point p and radius $||c-p||$.

If $\ell$ does not intersect D then we know immediately the side of $\ell$ that $c_D$ lies. Otherwise, let L be the intersection of $\ell$ with D. We compute $c_L$ for $\mathcal {P}$ such that it lies on L. Two cases arise (1) $c_L$ lies in the interior of L and (2) $c_L$ is one of the end-points of L.

Case 1: ($c_L$ lies in the interior of L) If $\mathcal {P}_{c_L}$ lie in a convex infinite wedge, formed by $\angle p_ic_Lp_j$ for points $p_i$ and $p_j$ in $\mathcal {P}_{c_L}$ for some i and j, then $c_D$ lies in the direction of mid-point of $p_ip_j$ from $c_L$. We can easily determine the existence of convex infinite wedge by a linear traversal over the points in $\mathcal {P}_{c_L}$. Otherwise, if the convex infinite wedge does not exist, $c_L$ is $c_D$.

Case 2: ($c_L$ is one of the end points of L) As in case 1, we see if all points of $\mathcal {P}_{c_L}$ lie inside any convex infinite wedge, formed by $\angle p_ic_Lp_j$ for points $p_i$ and $p_j$ in $\mathcal {P}_{c_L}$ for some i and j. If they do not then $c_L$ is $c_D$. Otherwise, we compute the circles $C_{p_i}(c_L)$ and $C_{p_j}(c_L)$. Center $c_D$ will lie in their intersection with D, say S, that is, $S = C_{p_i}(c_L) \cap C_{p_j}(c_L)\cap D$. Note that S does not intersect L other than at $c_L$ since $c_L$ is 1-center constrained on L. If S is completely outside D, except $c_L$, then $c_L$ is $c_D$, otherwise we know the side of L, and therefore $\ell$, that $c_D$ lies. Thus we have the following lemma.

Lemma 2

The location of $c_D$ with respect to $\ell$ can be computed in linear time. Moreover, if $c_D$ is on L then it can be computed in linear time.

We show how Lemma 2 can be used to compute $c_D$ in theorem below.

Theorem 1

Euclidean 1-center $c_D$ for $\mathcal {P}$ constrained on a disk D can be computed in O(n) time.

Proof

We pair the points as $(p_{2i-1}, p_{2i}), i = 1, \ldots , \lfloor \frac{n}{2} \rfloor$. Let ${\ell }_i$ be the perpendicular bisector of the pair $(p_{2i-1}, p_{2i})$. We compute the median slope s of all $\ell _i$. We rotate the x-axis to have slope s for the duration of iteration. We treat horizontal lines of the form $y =y_i$, and vertical lines of the form $x=x_i$, separately. Non-horizontal and non-vertical lines are paired as $(\ell _i,\ell _j)$ such that one has positive slope and another has negative slope. Let $(x_{ij},y_{ij})$ be the intersection point for pair $(\ell _i,\ell _j)$. Let $y_m$ be the combined median of $y_{ij}$’s for the line pairs $(\ell _i,\ell _j)$’s and $y_i$’s for the horizontal $\ell _i$’s. Let $\ell _x$ be the line $y=y_m$ parallel to x-axis.

By Lemma 2, we can find the location of $c_D$ with respect to line $\ell _x$ in O(n) time. If $c_D$ in on L then we are done. Otherwise, first consider the lines $\ell _i$’s that are parallel to $\ell _x$, and are on the side of $\ell _x$ that does not contain $c_D$. For each of these horizontal $\ell _i$’s, we can drop one point between $p_{2i}$ and $p_{2i-1}$. Secondly, among the intersecting pairs $(\ell _i,\ell _j)$, consider those for which corresponding $y_{ij}$ lies on the side of $\ell _x$ which does not contain $c_D$. We compute the combined median $x_m$ of the corresponding $x_{ij}$’s for these pairs and $x_i$’s for vertical $\ell _i$’s left earlier. By Lemma 2 we can find the location of $c_D$ with respect to line $x=x_m$ parallel to y-axis, denoted by $\ell _y$. If $c_D$ lies on $\ell _y$ then we are done. Again, we can drop one point for vertical $\ell _i$’s on the side of $\ell _y$ that does not contain $c_D$. Next, consider the pairs $(\ell _i, \ell _j)$ such that neither $y_{ij}$ lies in the same side of $\ell _x$ as $c_D$, nor $x_{ij}$ lies in the same side of $\ell _y$ as $c_D$. Note that $c_D$ will lie on one side of either $\ell _i$ or $\ell _j$ for each of these pairs. For either $\ell _i$ or $\ell _j$, one defining points is always nearer to $c_D$ than the other defining point. We can drop the nearer point. Thus we drop at least $\lfloor \frac{n}{16}\rfloor$ of the points of $\mathcal {P}$ for the next iteration. The whole iteration takes O(n) time. We repeat the iteration with truncated set of points until we can not drop any further points. When we can not drop any points, at most a constant number of points remain and we can compute $c_D$ in O(1) time in the last iteration. All the iterations together can be done in O(n) time.    $\square$

3 Minimum Enclosing Ball Whose Center Is Constrained to Lie on a Given Sphere

Let $\mathcal {P}$ be a set of n points in $\mathfrak {R}^3$, $\mathcal {P}=\{p_1, p_2, \dots , p_n\}$. Let $\mathcal {P}_x$ be the set of points in $\mathcal {P}$ farthest from point $x \in \mathfrak {R}^3$.

In this section, we consider the problem of finding the Euclidean 1-center, denoted by $c_S$, for $\mathcal {P}$ where $c_S$ is constrained to lie on a given sphere S. We show how we can solve this problem in O(n) time. We solve the following problems to achieve this.

Problem 2. Given a line segment L, find the Euclidean 1-center of $\mathcal {P}$, denoted by $c_L$, constrained in L, in $\mathfrak {R}^3$.

Problem 3. Given a disk D, find the Euclidean 1-center of $\mathcal {P}$, denoted by $c_D$, constrained in D, in $\mathfrak {R}^3$.

Problem 4. Given a sphere S, find the Euclidean 1-center ($c_S$) of $\mathcal {P}$, constrained in S, in $\mathfrak {R}^3$.

3.1 Computing Euclidean 1-Center Constrained in a Line Segment L in $\mathfrak {R}^3$

We pair the points $p_{2i-1}$, $p_{2i}$ for $i = 1, \ldots , \lfloor \frac{n}{2} \rfloor$. Let $H_i$ be the bisector plane of $p_{2i-1}p_{2i}$. If $H_i$ does not intersect the interior of L for some i, we can drop the point $p_{2i-1}$ or $p_{2i}$ which is never farther than the other point from L.

Let $q_i$ be the intersection points of $H_i$ with L for all $H_i$ that intersect L in the interior. Let q be the median of the $q_i$’s. We compute set $\mathcal {P}_{q}$. Let ${H}_{q}$ be the plane perpendicular to L at q. If $H_{q}$ partitions $\mathcal {P}_{q}$, then q is $c_L$. Otherwise $c_L$ and $\mathcal {P}_{q}$ lie on the same side of $H_{q}$. We consider all the $q_i$’s on the side of ${H_{q}}$ that does not contain $c_L$. We can delete one of the points $p_{2i-1}$ or $p_{2i}$ which is never farther from $c_L$ than the other as in the case of $\mathfrak {R}^2$. Thus we discard one point each for at least half of the $q_i$s, implying that we can reduce the size of set $\mathcal {P}$ by at least one-fourth. We iterate with the reduced set. When we do not drop any point we use any suitable algorithm to compute $c_L$ for the basis set of size O(1).

Lemma 3

Euclidean 1-center $c_L$ of $\mathcal {P}$ constrained on any given line segment L in $\mathfrak {R}^3$ can be computed in O(n) time.

3.2 Computing Euclidean 1-Center Constrained in a Disk D in $\mathfrak {R}^3$

Let D be the given disk in $\mathfrak {R}^3$. We give an algorithm to compute $c_D$. Let H be the hyperplane containing D. Let $\ell$ be any line in hyperplane H. Let $S_p(c)$ be the sphere centered at point p and radius $||c-p||$.

First we give a method to determine the location of $c_D$ in H with respect to $\ell$. If $\ell$ does not intersect D then we clearly know which side of $\ell$ does $c_D$ lies. Otherwise, let L be the intersection of D with $\ell$. We compute 1-center $c_L$ of $\mathcal {P}$ constrained on L by the algorithm of previous Sect. 3.1. We compute the set $\mathcal {P}_{c_L}$. Center $c_D$ lies in the intersection, let us call it I, of all $S_p(c_L)$ with D, where $p \in \mathcal {P}_{c_L}$, that is, $I = \cap _{p \in \mathcal {P}_{c_L}}{S_p(c_L)}\cap D$. Observe that I does not intersect L other than $c_L$, otherwise $c_L$ will not be the optimal constrained center, a contradiction. This suggests an $O(n\log n)$ algorithm for determining the side of $c_D$ in D with respect to L, if we compute the intersection of bounding half-planes of $S_p(c_L)$. But this is not acceptable as we need to do it on O(n) time. Hence, we solve a linear programming problem (LPP) to solve this subproblem efficiently in linear time. The LPP is given below.

Let $\overrightarrow{x}$ denote the vector from $c_L$ to yet unknown $c_D$. Let $\overrightarrow{a_y}$ be the vector from $c_L$ to any point $y \in \mathcal {P}_{c_L}$. Note that $||c_L-y|| \ge ||c_D-y||$ as y is an extreme point, implying that $c_D$ lies inside a ball. We can relax this condition to specify that $c_L$ lies in the halfspace determined by the tangential hyperplane of the ball at $c_L$. Thus the constraints of LPP are $\overrightarrow{x} \cdot \overrightarrow{a_y} \ge 0$, for all $y \in \mathcal {P}_{c_L}$. We add two extra constraints (i) $\overrightarrow{x}.h = 0$, h is normal of hyperplane H and (ii) if $c_L$ is on boundary of D, then $\overrightarrow{x} \cdot \overrightarrow{c_Ld} \ge 0$, where d is the center of disk D. If this LPP has a feasible solution for non-zero length of $\overrightarrow{x}$ then we know the location of $c_D$ with respect to L, otherwise if the LPP is infeasible then $c_L$ is $c_D$. The number of constraints in LPP is at most $|\mathcal {P}_{c_L}| + 2$ which is at most $n+2$. We can check feasibility of this LPP in linear time [4, 6, 11] (Fig. 1).

Lemma 4

The location of Euclidean 1-center $c_D$ of $\mathcal {P}$ constrained on any disk D in $\mathfrak {R}^3$ in H with respect to any line $\ell$ coplanar with D can be determined in O(n) time. Moreover, if $c_D$ lies on l then we can determine $c_D$ in O(n) time.

Fig. 1.

Determining the location of $c_D$ with respect to L

Fig. 2.

Determining the location of $c_S$ with respect to D

We use Lemma 4 to design a prune and search algorithm for computing $c_D$. We pair the points $(p_{2i-1},p_{2i})$ for $i = 1, \ldots , \lfloor \frac{n}{2} \rfloor$. Let $H_i$ be the bisector plane of pair $(p_{2i-1},p_{2i})$. If $H_i$ does not intersect interior of D then we can drop one of the points in the pair which is never farther from $c_D$ than the other point. Next we consider all $H_i$’s that intersect interior of D. We compute the intersections of $H_i$ with H, let the intersection be the line $\ell _i$. For simplicity, assume that H is the xy-plane (Fig. 2).

As in Sect. 2, we transform x-axis to median slope of lines $\ell _i$’s and pair lines $\ell _i$ according to the median slope leaving vertical and horizontal lines. We calculate intersection points of the paired lines. Then we compute the similar line $\ell _x$ of Sect. 2 for $\ell _i$’s. This line will divide intersections and horizontal lines by half. By Lemma 4, we know the location of $c_D$ with respect to line $\ell _x$. We can drop one point each corresponding to some of the horizontal $\ell _i$’s and therefore $H_i$’s. Next we compute the line $\ell _y$ similar to Sect. 2 for $\ell _i$’s. We take all the intersections on the side of $\ell _x$ that does not contain $c_D$, take all vertical $\ell _i$’s, and choose $\ell _y$ parallel to y-axis dividing these intersections and vertical lines into half. Again by Lemma 4, we know the location of $c_D$ with respect to line $\ell _y$. We can drop one point each corresponding to some of the vertical $\ell _i$’s and some of the line pairs $(\ell _i,\ell _j)$’s. Thus, there will be corresponding number of at least $\lfloor \frac{n}{8}\rfloor$ lines $\ell _i$’s, and therefore planes $H_i$’s, for which we can drop the nearer one of the defining pair of points. In all, we drop at least $\lfloor \frac{n}{16}\rfloor$ points of $\mathcal {P}$ in each iteration. When we drop no points we use any suitable algorithm to compute $c_D$ for O(1) number of points. The complete algorithm runs in linear time.

Lemma 5

Euclidean 1-center $c_D$ of $\mathcal {P}$ constrained on any planar disk D in $\mathfrak {R}^3$ can be computed in O(n) time.

3.3 Computing Euclidean 1-Center Constrained in a Sphere S in $\mathfrak {R}^3$

As in the other problems in this paper, we use prune and search technique to compute $c_S$. In order to successfully discard a fraction of points from $\mathcal {P}$ we need to determine the location of $c_S$ with respect to a given hyperplane H in $\mathfrak {R}^3$.

If H does not intersect the interior of S then we immediately know the location of $c_S$ with respect to H. Otherwise, let D be the circular disk which is intersection of H with S. We compute Euclidean 1-center $c_D$ for $\mathcal {P}$ constrained on D as in previous Sect. 3.2. $c_S$ lies in the intersection I of $S_p(c_D)$’s where p is a point in $\mathcal {P}_{c_D}$. I does not intersect D other than $c_D$ as $c_D$ is the Euclidean 1-center constrained on D. To determine the location of $c_S$ with respect to H efficiently we solve an LPP as in Sect. 3.2. The constraints are $\overrightarrow{x} \cdot \overrightarrow{a_y} \ge 0$ similarly, where $\overrightarrow{x}$ is the vector from $c_D$ to $c_S$, and $a_y$’s are vector from $c_D$ to $y \in \mathcal {P}_{c_D}$. If $c_D$ is on the surface of S we add another constraint $\overrightarrow{x} \cdot \overrightarrow{c_ds} \ge 0$ where s is the center of S. If this system of constraints has a feasible solution other than $c_D$ then we determine the location of $c_S$ with respect to H. If the constraints are infeasible than $c_D$ is $c_S$. We can do this in linear time using linear time algorithm for LPP in fixed dimensions [4, 6, 11].

Lemma 6

Given a sphere S and a hyperplane H we can determine in linear time the location of $c_S$ with respect to H in $\mathfrak {R}^3$. Moreover, if $c_S$ lies on H then $c_S$ can be determined in linear time.

We use Lemma 6 to design a prune and search algorithm to compute $c_S$.

First we pair the point in $\mathcal {P}$ arbitrarily and compute their bisector planes $H_i$, $1 \le i \le \lfloor n/2 \rfloor$. If $H_i$ does not intersect the interior of sphere S, then one of the corresponding pair of points on the same side of the plane as S can be dropped. Consider all $H_i$’s that intersect S in the interior. For convenience let us assume that all $H_i$’s intersect S in the interior. We give an algorithm similar to that given by Megiddo [11] to find a constant fraction of $H_i$’s for which location of $c_S$ is determined in linear time.

We compute the intersections of $H_i$’s that intersect interior of S with the xy-plane. Let the intersection be straight line $\ell _i$ corresponding to each such $H_i$. We compute the median slope $s_m$ of lines $\ell _i$ in the xy-plane. We transform the x-axis to have slope $s_m$. We pair planes $H_i$ and $H_j$ such that $\ell _i$ has a negative slope in the xy-plane and $\ell _j$ has a positive slope. We treat horizontal and vertical $\ell _i$’s separately. Next we compute planes $H_{ij}^{1}$ and $H_{ij}^2$ through the intersection of $H_i$ and $H_j$ parallel to x-axis and y-axis respectively. See Fig. 3.

First consider the yz-plane. $H_{ij}^{1}$’s are perpendicular to this plane. We compute intersection of $H_{ij}^{1}$’s with yz plane and denote the lines by $l_{ij}^{1}$. We also compute intersection $l_i^1$ of $H_i$’s with yz planes corresponding to horizontal $\ell _i$’s above. Let us call this set of lines $l_{ij}^{1}$ and $l_i^1$ L Similar to computing lines $\ell _x$ and $\ell _y$ for $\mathfrak {R}^2$ in Sect. 2, we compute line $\ell _y$ and $\ell _z$ for $\mathfrak {R}^3$ in succession. First we compute $\ell _y$ in yz-plane for lines in L. Let the plane that is parallel to x-axis and passes through $\ell _y$ be $H_y$. By Lemma 6 we can determine the location of $c_S$ with respect to $H_y$. We compute line $\ell _z$ in yz-plane for L. Let the plane that is parallel to x-axis and passes through $\ell _z$ be $H_z$. By Lemma 6 we determine the location of $c_S$ with respect to $H_z$. After this, we know the quadrant of $H_y$ and $H_z$ that contains $c_S$. We determine the location of $c_S$ with respect to at least one eighth of the lines $l_{ij}^{1}$’s, $l_i^1$’s, and therefore $H_{ij}^{1}$’s. See Fig. 4.

Fig. 3.

Pairing of $H_i$ and $H_j$, and computation of $\ell ^1_{ij}$ and $\ell ^2_{ij}$

Fig. 4.

Determining the location of $c_S$ with respect to a fraction of planes $H^1_{ij}$’s

Next we consider the xz-plane. $H_{ij}^{2}$’s are perpendicular to this plane. We take only those $H_{ij}^{2}$’s for which we have determined the location of $c_S$ with respect to corresponding $H_{ij}^{1}$’s. There will be at least $\lfloor n/16 \rfloor$ of them.

We compute intersection of $H_{ij}^{2}$’s with xz plane and denote the lines by $l_{ij}^{2}$. We also computer intersection $H_i$’s corresponding to vertical $\ell _i$’s in xy-plane above and denote the intersection lines by $l_i^2$. Similar to computing lines $\ell _y$ and $\ell _z$ in previous discussion we now compute lines $\ell '_x$, $\ell '_z$ and corresponding y-parallel planes $H'_x$, $H'_z$, such that one-eighth (total 1/64-th) of the lines $l_{ij}^{2}$’s and $l_i^2$’s do not intersect the quadrant defined of $H'_x$, $H'_z$ containing $c_S$.

Thus we have at least total $\lfloor n/128 \rfloor$ x-parallel or y-parallel $H_i$’s with respect to which $c_S$ is located, or pairs of $H_i$ and $H_j$ such that $c_S$ is known to be contained in one of the quadrants of $H_{ij}^{1}$ and $H_{ij}^{2}$. In the latter case, it is interesting to note that each quadrant contains only one of $H_i$ or $H_j$ and therefore does not intersect with the other one. So, as a consequence we can determine the location of $c_S$ with respect to one of $H_i$ or $H_j$. Thus we can drop one of the corresponding pair of points that is never farther from $c_S$ than the other point. Therefore in total we are able to drop at least $\lfloor n/128 \rfloor$ points from $\mathcal {P}$. We repeat these steps till there are no more points to drop. Then we compute $c_S$ by any simple algorithm as the set is reduced to size O(1).

Theorem 2

Euclidean 1-center $c_S$ for $\mathcal {P}$ constrained on a sphere S can be computed in O(n) time in $\mathfrak {R}^3$.

4 Other Related Problems of Minimum Enclosing Balls and Minimum Intersecting Disks

In this section, we show how the techniques of Sects. 2 and 3 can be applied to solve several other facility location problems in linear time.

4.1 Minimum Enclosing Ball of Set of Points Whose Center Is Constrained to Lie on a Given Ball in $\mathfrak {R}^d$

We use the familiar techniques of prune and search method to solve the problem of computing minimum enclosing ball of set of points in $\mathfrak {R}^d$ whose center is constrained in a given ball recursively. We redefine the problem as computation of Euclidean 1-center $c_B$ of a point set $\mathcal {P}$ in $\mathfrak {R}^d$ in linear time where $c_B$ is constrained inside a given ball B of dimension k, $0 \le k \le d$ in $\mathfrak {R}^d$. In this paper we have shown the base cases of $k=2$ and $k=3$. The cases of $k=0$ and $k=1$ are taken care of in the discussion of the cases in higher dimensions.

Inductively assume that we are able to solve the problem for balls of dimension $k-1$ in linear time. Also we assume we know how to query a fixed fraction of some $A_{k-1}$ hyperplanes to determine the location of $c_B$ with respect to $B_{k-1}$ fraction of hyperplanes. We show in brief how we can use the solution to solve the problem for a ball B of dimension k in linear time. First we pair the points arbitrarily and get bisector hyperplanes $H_i$’s. We look only at the affine plane of ball B which is of dimension k. The coordinates in this affine plane are denoted by x, y and Z, where Z are rest of $k-2$ coordinates. Next as in Sect. 3, we compute the intersection of $H_i$’s on xy-plane. We modify the x-axis to pair hyperplanes with positive and negative slopes in xy- plane. x and y parallel hyperplanes are treated separately. Next we compute hyperplanes $H_{ij}^1$ and $H_{ij}^2$ of dimension $k-1$ parallel to x-axis and y-axis respectively for $H_i$ and $H_j$ in the pair above. Lines $\ell _{ij}^1$ and $\ell _{ij}^2$ will be of dimension $k-2$. We also have line $\ell _i^1$ and $\ell _i^2$ corresponding to horizontal and vertical intersections in xy-plane. We recursively query $A_{k-1}$ planes in $(k-1)$-space yZ-plane, determining location of $c_B$ with respect to $B_{k-1}$ fraction of hyperplanes $\ell _{ij}^1$’s and $\ell _i^1$’s and then $A_{k-1}$ planes in $(k-1)$-space xZ-plane, determining location of $c_B$ with respect to $B_{k-1}^2$ hyperplanes $\ell _{ij}^2$’s and $\ell _i^2$’s, to drop one point corresponding to $B_{k-1}^2$ planes $H_i$’s. Thus $A_k=2A_{k-1}$ and $B_k=B_{k-1}^2$.

We can use the feasibility of an LPP as in Sects. 3.2 and 3.3 (except that we add constraints to keep vector x in the k-dimensional affine space), to determine the location of $c_B$ in affine space of dimension k with respect to any query hyperplanes of dimension $k-1$. Thus we will be able to drop a finite fraction of points. This fraction is double exponent on d but can be improved using techniques by Dyer [6]. Repeating the process until no points can be dropped and then applying any simple algorithm gives us a linear time algorithm.

4.2 Minimum Intersecting Ball of Set of Hyperplanes Whose Center Is Constrained to Lie on a Given Ball in $\mathfrak {R}^d$

In this subsection we compute the minimum intersecting ball of set of hyperplanes whose center is constrained on a given ball in $\mathfrak {R}^d$. We solve this problem recursively similarly to method of previous section. We pair the hyperplanes arbitrarily and compute the orthogonal pair of bisector hyperplanes. If we are able to find the location of center of intersecting ball with respect to both of the bisector hyperplanes then we can drop one of the input hyperplanes. So, first we take one of the bisector hyperplanes of each pair, solve the query for a small fraction of these, take the companion bisector hyperplane and solve the query for a still smaller fraction of these. Thus, we are able to determine the location of the center of constrained minimum intersecting ball with respect to a fraction of both of the orthogonal pair of bisector hyperplanes. We can discard the hyperplane that is always the nearer of the two defining bisector. Repeating and solving the base case gives us a linear time algorithm for this problem.

If the set contains both points and hyperplanes we drop a fraction of points and hyperplanes in two successive steps. First we consider only the set of points and then we consider only the set of hyperplanes. The query version of the problem in smaller dimension is also treated similarly.

Fig. 5.

Constrained minimum intersecting circle for convex polygons in plane.

Fig. 6.

1-center with constant number of non-linear convex constraints $f_j(x) \le 0$ in $\mathfrak {R}^2$.

4.3 Minimum Intersecting Circle of Set of Convex Polygons Whose Center Is Constrained to Lie on a Given Disk in $\mathfrak {R}^2$

In this subsection we consider the case of constrained minimum intersecting circle for set of convex polygons in plane (Fig. 5). We solve this problem by an algorithm that is similar to the algorithm by Jadhav et al. [8]. We have shown how to solve the problem of computing minimum enclosing circle constrained to lie on a given disk for a set of points. This is same as constrained minimum intersecting circle. In the previous section we have shown how to compute minimum intersecting circle for lines. We first extend our result to set of half plane, line-segments, rays, and wedges. We represent the convex polygon as the intersection of wedges, one for each vertex. In every iteration a fraction of wedges is dropped, or replaced by a half plane, line, a ray, a line segment or a point. At any step we have a set of points, line segments, rays, lines, wedges, and half-planes. We apply the algorithm by taking similar type of objects at a time. Thus we are able to convert or drop a fixed fraction of these objects at every iteration. We can improve the efficiency by using weights. This gives us a linear time algorithm for the problem.

4.4 Euclidean 1-Center for $\mathcal {P}$ With Constant Number of Non-linear Convex Constraints in $\mathfrak {R}^d$

We can use techniques described in this paper when facility has to be located inside a convex region bounded by $m=O(1)$ number of non-linear convex constraints, $f_j(x) \le 0$, with some computability assumptions (Fig. 6). The computability assumptions are that we can compute the following in O(1) time, where $x\in \mathfrak {R}^d$ and $1\le j\le m$:

A1. whether $f_j(x)>0$, $f_j(x)=0$, or $f_j(x)<0$, and if $f_j(x)=0$, a hyperplane at x tangential to convex region $f(y)\le 0, y\in \mathfrak {R}^d$, and

A2. if it exists, constrained 1-center further constrained in an affine space for O(1)-size input set, or report the non-existence, if it does not.

We can have an O(1) total number of these additional constraints. Thus we solve the following optimization problem for c:

$$\begin{aligned}&\min \nolimits _{c \in \mathfrak {R}^d} \max \nolimits _{1 \le i \le n} ||c-p_i|| \\&\qquad f_j(c)\le 0, 1\le j \le m \end{aligned}$$

where $f_j$’s are non-linear convex constraints with computability assumptions. Examples of non-linear convex constraints with computability assumptions include ellipsoids, paraboloids, cylinder, polyhedra of O(1) size, etc.

As noted earlier, we need to solve the corresponding problem in $\mathfrak {R}^{k}$ constrained in an affine plane $H_k$ for any dimension k, $1 \le k \le d-1$. We can represent the constraints when we are solving the problem in dimension k by pairing the constraints with the hyperplane $H_k$.

Let $c_k(H_k)$ be the 1-center of $\mathcal {P}$, such that 1-center is constrained on k-dimensional affine plane $H_k$. Euclidean 1-center of $\mathcal {P}$ in $\mathfrak {R}^d$ will be $c_d(\mathfrak {R}^d)$. We show briefly how these type of problems can be solved in linear time for dimension k, $1\le k \le d-1$. In the algorithm mentioned in the Sects. 3.1, 3.2, and 3.3, we frequently check whether a bisector intersects the constraint interval, disk, and ball or not. With our computability assumption for non-linear convex constraints we can not do this any more. Instead we do not check if bisectors do not intersect the convex constraint region at all. However, for $k > 1$, we need to ensure that $c_{k-1}(H_{k-1})$ satisfies non-linear convex constraints, if it exists. For $k=1$, in $\mathfrak {R}^1$ when we are computing $c_1(H_1)$, every time we check the feasibility for the median q of intersections of bisectors with the line $H_1$, whether $f_j(q) \le 0$ for every j. This can be done by computability assumption A1. If q does not satisfy some constraint, then we need to determine the side of q with respect to line $H_1$ that $c_1(H_1)$ lies. For this we solve the 1-center problem by computability assumption A2 in $\mathfrak {R}^d$ for set $\{q\}$ constrained on line $H_1$. The solution will give us the direction $c_1(H_1)$. Finally, when we do not drop any point, we can use computability assumption A2 to compute 1-center constrained on $H_1$ with constraints $f_j$’s, if it exists, and report the non-existence, if it does not exist.

Now let us suppose $k>1$. In the algorithm whenever we solve the subproblem in dimension $(k-1)$, for any affine plane $H_{k-1}$, we shall get a $c_{k-1}(H_{k-1})$ satisfying the $f_j$ constraints, if it exists. Then we proceed with the LPP, where we may need a tangential hyperplane which is provided by computability assumption A1. If $c_{k-1}(H_{k-1})$ does not exist, then we can take a point $q \in H_{k-1}$, solve the problem using computability assumption A2 for set $\{q\}$ and know the side of affine plane $H_{k-1}$ that 1-center $c_k(H_k)$ lies with respect to $H_k$. The correctness of this method can be proved using induction, where base case for induction is $k=1$. We again need only assumption A2, when at the end of the algorithm no further points are dropped, and we need to compute 1-center of input size O(1) constrained in $H_k$ and satisfying constraints $f_j$’s. We can prove the optimality of $c_k(H_k)$ by induction on k. Thus we have the following theorems.

Theorem 3

Minimum intersecting circle for a set of points and hyperplanes where 1-center satisfies constant number of non-linear convex constraints with computability assumptions can be computed in O(n) time in $\mathfrak {R}^d$.

Theorem 4

Minimum intersecting circle for a set of convex polygons where the center of minimum intersecting circle satisfies non-linear convex constraints with computability assumptions can be computed in O(n) time in $\mathfrak {R}^2$.

As a side note, if computability assumptions have $\varOmega (1)$ computations then also we can compute 1-center but the $\varOmega (1)$ complexities will be reflected in the overall complexity of the algorithm as a multiplicative factor, but the algorithm would still be similar.

5 Conclusions

In this paper we solve several versions of facility location problems for which the facility is constrained inside a convex region. These problems have not been attempted previously. In particular we solve the Euclidean 1-center problem for points in $\mathfrak {R}^2$ and $\mathfrak {R}^3$ constrained in a disk and ball respectively. The corresponding Euclidean 1-center problem to compute the center such that the center lies on the circle in sub $O(n\log n)$ time is still open. We looked at this problem but same techniques as this paper do not seem to be applicable as the parametric distance function on the circumference of the circle is not convex.

We also generalize algorithm to solve the problem of computing constrained minimum intersecting balls in $\mathfrak {R}^d$ for a heterogeneous set of points and hyper planes. We also show that the constraint region can be other type of simple convex geometric objects and still we can compute the constrained minimum intersecting balls in linear time. We also show how we can compute the constrained minimum intersecting disk for a set of convex polygons in plane. The efficiency of algorithms, as dependency on d, presented in this paper can be improved, from $2^{2^d}$ to $3^{d^2}$, if we use techniques by Dyer [6].