Abstract
We study the problem of searching for a target at some unknown location in \(\mathbb {R}^d\) when additional information regarding the position of the target is available in the form of predictions. In our setting, predictions come as approximate distances to the target: for each point \(p\in \mathbb {R}^d\) that the searcher visits, we obtain a value \(\lambda (p)\) such that \(|p\varvec{t}|\le \lambda (p) \le c\cdot |p\varvec{t}|\), where \(c\ge 1\) is a fixed constant, \(\varvec{t}\) is the position of the target, and \(|p\varvec{t}|\) is the Euclidean distance of p to \(\varvec{t}\). The cost of the search is the length of the path followed by the searcher. Our main positive result is a strategy that achieves \(O(c^d)\)-competitive ratio, even when the constant c is unknown. We also give a lower bound of roughly \((c/4)^{d-1}\) on the competitive ratio of any search strategy in \(\mathbb R^d\), assuming that \(c\ge 4\).
Similar content being viewed by others
1 Introduction
The problem of searching for a target positioned at some unknown location in some region is a classic search game problem that has been well-studied in both fields of Computational Geometry and Operations Research. The problem comes in many different versions, such as linear search (i.e., searching for a target on a line) [6, 7, 9, 16], searching in the plane [4, 8, 17, 23], searching in concurrent rays [4, 15, 16], and searching inside polygonal regions [27, 33]. The book by Alpern and Gal [1] provides an extensive overview of general search games, while Ghosh and Klein [18] survey search problems in planar domains.
The searcher starts from some given position, follows some path according to some strategy until the target, usually a point, is reached or detected, for some appropriate definition of “detection”. In 1-dimensional settings, e.g., an infinite line, one usually requires that the searcher passes through the target point. In the plane one usually requires that the searcher is within some distance of the target, or sees the target, if there are obstacles, or that the target lies on the segment connecting the searcher’s current and starting positions [17, 18, 29].
The cost of the search is the length of the path followed by the searcher and the objective is to find an efficient search strategy. Efficiency is usually measured by the competitive ratio, which, in this setting, is the ratio of the length of the path of the searcher to the actual Euclidean distance of the starting position to the target.
In this work, we consider the problem of finding a target point \(\varvec{t}\) in Euclidean space \(\mathbb {R}^d\) when additional information regarding the position of the target is available in the form of predictions. Here, the predictions are the approximate distance to \(\varvec{t}\) for all points visited during the search, e.g., a value between, say, \(|p\varvec{t}|\) and \(2|p\varvec{t}|\) for each point p visited, where \(|p\varvec{t}|\) is the Euclidean distance between p and t. Such an estimate could be obtained for example in a scenario where one takes into account the strength of a signal broadcasted by the target.
Algorithms with predictions is a concept that has been introduced relatively recently; see the survey by Mitzenmacher and Vassilvitskii [31]. The general idea is that on top of the usual input data we are also given additional and possibly inaccurate (noisy) information, the prediction, that should assist the algorithm to be more effective. The improvement in performance depends on the accuracy of the prediction.
1.1 Problem Setup
We consider the following search problem in \(\mathbb R^d\). Assume that there is a fixed but unknown target point \(\varvec{t}\in \mathbb R^d\). Without loss of generality, we start the search at the origin, which we denote by \(\varvec{o}\). We want to find a curve \(\gamma \) that starts at \(\varvec{o}\) and ends at \(\varvec{t}\). The cost of the search is the Euclidean length of the curve \(\gamma \).
As we search for the target, we have approximate information about the distance to it from each point that we have visited so far. More precisely, we assume that there is a constant \(c\ge 1\) and an unknown function
We refer to such a function \(\lambda \) as a c-prediction for the target \(\varvec{t}\). The constant c is the prediction factor of \(\lambda \). See Fig. 1 for an example in \(d=1\). Note that for \(c=1\), the function \(\lambda \) gives the exact distance to the target.
For each point p along the search path we have traversed so far, we obtain the value \(\lambda (p)\), and the search strategy decides how to continue the search depending on that information. We know when we have reached the target because \(\lambda (p)=0\) holds only when \(p=\varvec{t}\).
As it is common in search games, we are interested in the competitive ratio of the search strategy: how does the length of the search path compare to the straight-line distance from the origin to the target? To formalize this, for each target \(\varvec{t}\in \mathbb R^d\) and each constant \(c\ge 1\), we consider the family \(\Lambda (\varvec{t},c)\) of c-predictions for \(\varvec{t}\), that is, functions satisfying condition (1). The family of c-prediction functions is \(\cup _{\varvec{t}\in \mathbb R^d} \Lambda (\varvec{t},c)\).
A search strategy S is \(\alpha =\alpha (S,c,d)\) competitive if for all \(\varvec{t}\in \mathbb R^d\) and all \(\lambda \in \Lambda (\varvec{t},c)\), the length of the path defined by S to reach \(\varvec{t}\) from \(\varvec{o}\) is at most \(\alpha |\varvec{o}\varvec{t}|\). Note that the prediction factor c may be known or unknown to the search strategy.
1.2 Our Contribution
Our main contributions are the following:
-
We introduce a natural, new search problem in \(\mathbb R^d\) for \(d\ge 1\), under a predictions model where we have approximate information about the distance to the target.
-
We show that for each dimension d and each constant prediction factor \(c\ge 1\) there is a search strategy with competitive ratio smaller than \((5c)^{d+1}\). To achieve this, we use \(\varepsilon \)-nets from metric spaces, also known as r-nets, and provide a path of finite length but an infinite number of pieces. This result holds assuming that we know the prediction factor c. For unknown prediction factor, a slightly different search strategy leads to a competitive ratio smaller than \((10c)^{d+1}\). Both of these ratios can be improved to \(O(c^d)\). These results are given in Sect. 4.
-
We show that for \(c\ge 4\), any deterministic search strategy in \(\mathbb R^d\) with c-predictions will have a competitive ratio of at least \((c/4)^{d-1}\cdot \min \{\sqrt{\pi /d},1\}\). For this result, we construct an infinite family of c-predictions and use a volume argument to give a lower bound on the length of any path that can discern which c-prediction from the family is the actual one. The approach is motivated by the techniques used to obtain approximation algorithms for the Euclidean Traveling Salesperson with Neighbourhoods. However, in our setting we have an infinite number of neighbourhoods, one for each c-prediction. With a slightly worse constant, the lower bound also holds for randomized search strategies. This lower bound is shown in Sect. 5.
Additionally, we give several basic properties of the model. For example, we show that without a prediction function throughout the whole search, we cannot find the target using a path of bounded length, and having an infinite number of pieces (segments) in the search path is unavoidable. We also show that we may assume that the prediction function is continuous. We also note that when \(c=1\), i.e., we have exact information about the distance to the target, the target can be reached with competitive ratio arbitrarily close to 1. These results are presented in Sect. 3.
To our knowledge, this is the first search problem in Euclidean spaces with \(d\ge 2\) where a search point reaches a target point with constant competitive ratio; see the discussion below about related work. For our upper bounds we use bounds on the cardinality of \(\varepsilon \)-nets. For the sake of simplicity in the calculations, we use suboptimal but simple-to-parse estimates in the simplifications and the cardinality of \(\varepsilon \)-nets. Similarly, in our lower bounds we also use volume estimates that are easier to manipulate. In any case, our upper and lower bounds for the best competitive ratio are still far apart.
Our model, as presented, is continuous and has the advantage of being scale-free, a desired mathematical property. While the searcher may receive predictions at any point it wishes along the search path, in our strategies the searcher receives predictions only at the endpoints of the straight-line segments that comprise the path. Hence, only an enumerable set of predictions is used.
There are several natural variants of the model, and some of them may be of interest in more practical scenarios. A first variant is to assume that the target has integer coordinates or that the target can be detected when the searcher is within a given distance from it. This model is not scale-free anymore. Our search strategies can be easily modified to have a finite number of steps in this setting. The lower bound holds in this setting too, albeit with a slightly worse constant. A second variant is to assume that information about the distance is given only at regular intervals; to interpret this setting it is more convenient to assume that the searcher moves at unit speed and that the estimated distance to the target is available to the searcher at regular time intervals. In this case, it is meaningful to define the competitive ratio by comparing the travel times to reach the target. It follows from our results that in this setting no bounded competitive ratio is possible. If we mix the two variants we have mentioned, then simple modifications of our search strategies achieve bounded competitive ratio. Another variant is to allow for underestimates of the actual distance (in addition to the default overestimates). Our positive and negative results also hold in this setting, with slightly different constants. These variants are discussed along the text, mostly in Sect. 4.1.
1.3 Related Work
For linear search, when the exact distance to the target is known, one can easily find the target by walking at most three times this distance. When the distance to the target is unknown, Beck and Newman [7] and later Baeza-Yates at al. [4] showed that a simple deterministic doubling strategy has competitive ratio 9; here, a lower bound on the distance to the target is assumed, otherwise there is no search strategy with constant competitive ratio. There are also other similar strategies with the same competitive ratio [10, 18]. Moreover, various approaches [4, 7, 22, 28] show that 9 is the best possible deterministic competitive ratio for the problem. Finally, Gal [17] and later Kao et al. [25] gave an optimal randomized strategy with competitive ratio of approximately 4.5911.
Gal [15, 16] introduced the problem of searching for a target on multiple rays that are concurrent at the starting position and gave an optimal strategy for the case where the distance to the target is unknown. This result was rediscovered by Baeza-Yates et al. [4]. Additionally, the randomized strategy for linear search generalizes and gives an optimal strategy for this version too [17, 24, 25].
Baeza-Yates et al. [4] also considered the problem of finding a target with integer coordinates in the plane and presented various search strategies. When the distance to the target is known, it is also easy to get an optimal strategy. However, when the distance is unknown, and with no additional information available, no search strategy can have constant competitive ratio as there are \(\Theta (n^2)\) integral points within distance at most n from the origin and any search strategy has to visit all of them in some order. For the natural extension of the problem in \(\mathbb R^d\), the latter generalizes to any \(d\ge 3\), as there are \(\Theta (n^{d})\) integral points within distance at most n from the origin. When we are in \(\mathbb R^d\) and the distance to the target is known, we hit a classical problem in Number Theory: on how many ways can we express a positive integer as sum of d squares of integers. For \(d\ge 5\), there is no search strategy with constant competitive ratio as there are there are \(\Omega (n^{d/2-1})\) integral points at distance exactly n from the origin; see, for example, Vaughan and Wooley [35].
In another variant of the problem in the plane by Gal [17], the searcher travels along a path until the target lies on the segment connecting the searcher’s current and starting positions, essentially sweeping around its starting position with an infinitely elastic cord until the target is swept. For this problem, Gal [17] gave a spiral search strategy achieving a competitive ratio of \(17.289{\ldots }\), while Langetepe [29] showed that this ratio is optimal.
Hipke et al. [22] considered linear search when the target is at distance at least 1 and at most \(D\ge 1\) from the starting point, where D is known at the start of the search. Bose et al. [10] provided a more careful analysis using the roots of a recursive sequence of polynomials and gave better lower and upper bounds on the competitive ratio with dependence on D. López-Ortiz and Schuierer [30] considered also this setting, for the case of concurrent rays. Compared to these works, there are two main differences in our work. Firstly and most importantly, we have a prediction all the way through the search, while they have a prediction only at the start. Secondly, we consider the problem in more general settings, namely in \(\mathbb R^d\) for arbitrary d. An upper bound at the start does not suffice to find a point when when \(d>2\) or when \(d=2\) and \(c>1\). (If \(d=2\) and the exact distance is known, the problem can be easily solved since the target has to lie on a known circle, and that is the only additional instance that is solvable.)
Banerjee et al. [5] considered the problem of finding a target in a graph with information about the distance to the target. In their model, the target is at one vertex of the graph and each vertex has a value stored that is made available only when the searcher is at an adjacent vertex. For most vertices, the value stored at a vertex is the true distance from the vertex to the target, but for some vertices the value is wrong. Contrary to our setting, they do not assume a bounded error for the information at each vertex, but that the information is wrong at a bounded number of nodes. The bound on the number of nodes with wrong information then appears in the bound for the length of the search path.
Finally, Angelopoulos [2, 3] gave strategies for linear and multiple-ray search under a different model where a one-off, possibly erroneous hint or prediction on the target’s position is given at the start of the search. The prediction can be positional, directional, or, in general, a k-bit string encoding answers to k binary queries and the measure of the performance of a strategy is a trade-off between the competitive ratio under error-free prediction and that under erroneous prediction.
2 Notation and Preliminaries
Since the dimension d is always fixed and clear from the context, we drop in the notation the dependency on d.
The ball centered at \(p\in \mathbb R^d\) with radius r is \(B(p,r)=\{ q\in \mathbb R^d\mid |pq|\le r \}\). We will also consider the spherical shells \(S(p,r_1,r_2)= \{ q\in \mathbb R^d\mid r_1\le |pq|\le r_2 \}\). A spherical shell in the plane is an annulus. For a c-prediction function \(\lambda \), whenever we are at a point \(p\in \mathbb R^d\), we get a prediction \(\lambda (p)\) and we deduce that the target point \(\varvec{t}\) lies in the spherical shell \(S(p,\lambda (p)/c, \lambda (p))\). See Fig. 4.
Note that we have made a modeling decision, namely we have assumed that there is an unknown function \(\lambda \) such that at each point p we get the prediction \(\lambda (p)\). In a more general setting, the c-prediction may not be a function, i.e., it could happen that we visit the same point p multiple times and at each time we get a different estimate of the distance from p to the target. However, getting a different estimate can only help, as it provides more information: if we get two different c-predictions \(\lambda \) and \(\lambda '\) at different times at the same point p, then we know that the target lies in the spherical shell \(S(p,\max \{\lambda ,\lambda '\}/c, \min \{\lambda ,\lambda '\})\). This is more information than what we get if \(\lambda '=\lambda \) because then we can only conclude that the target lies in \(S(p,\lambda /c,\lambda )\), which is strictly larger. Thus, when searching for an optimal search strategy, we can assume that each time we visit the same point we get the same prediction. In particular, a search strategy could simply ignore the information obtained in the second and subsequent visits to the same point.
A path in \(\mathbb R^d\) is a continuous function \(\pi :[0,1] \rightarrow \mathbb R^d\). The paths in our search strategies will consist of an infinite number of straight-line segments and will exhibit a Zeno-like phenomena: they make an infinite number of turns in finite time and length. To show that the paths we define reach the target, we will use the following property, whose proof is an standard argument in continuity.
Lemma 1
Let \(\pi :[0,1] \rightarrow \mathbb R^d\) be a path. Assume that there is a point \(p\in \mathbb R^d\) with the following property: for each \(\varepsilon >0\) there exists some \(\delta \in (0,1]\) such that the subpath \(\pi ([1-\delta ,1])\) is contained in \(B(p,\varepsilon )\). Then \(\pi (1)=p\), that is, p is the endpoint of the path \(\pi \).
We will use \(\varepsilon \)-nets from metric space theory: An \(\varepsilon \)-net for the ball B(p, r) is a subset N of points from B(p, r) such that (i) each point of B(p, r) is at distance at most \(\varepsilon \) from some point of N, and (ii) each two distinct points of N are at distance at least \(\varepsilon \). Condition (i) can be equivalently be stated as \(B(p,r)\subseteq \bigcup _{q\in N}B(q,\varepsilon )\). Condition (ii) is equivalent to telling that the balls \(B(q,\varepsilon /2)\), where \(q\in N\), are pairwise interior disjoint.
The following bound on \(\varepsilon \)-nets follows from a well-known technique using volumes. We will not use the lower bound, but we include it to show that the upper bound is a reasonable estimate.
Lemma 2
In \(\mathbb R^d\), for each \(\varepsilon \le r/2\), a ball of radius r has a \(\varepsilon \)-net with at least \((r/\varepsilon )^d\) and at most \((5r/2\varepsilon )^d\) elements.
Proof
Using scaling and translation, it suffices to show the result for the unit ball centered at the origin, \(B(\varvec{o},1)\), and for \(\varepsilon \le 1/2\).
Let N be an inclusion-wise maximal subset of points from \(B(\varvec{o},1)\) such that any two points are at distance at least \(\varepsilon \). We claim that N is a \(\varepsilon \)-net. By definition, N satisfies property (ii) of the \(\varepsilon \)-net definition above. Since by maximality we cannot add any other point of \(B(\varvec{o},1)\) to N, each point of \(B(\varvec{o},1)\) has some point of N at distance at most \(\varepsilon \), and thus property (i) is also satisfied.
It remains to bound from below and above the cardinality of N. Because of property (i), the ball \(B(\varvec{o},1)\) is contained in \(\bigcup _{q\in N} B(q,\varepsilon )\). Using the constant \(V_d=\tfrac{\pi ^{d/2}}{\Gamma (d/2+1)}\) that gives the volume of the unit ball in \(\mathbb R^d\), we then have
On the other hand, property (ii) implies that the family of balls \(\{ B(q,\varepsilon /2) \mid q\in N\}\) are pairwise interior disjoint. Each such ball is contained in the enlarged ball \(B(\varvec{o}, 1+\varepsilon /2)\), and therefore
where in the last inequality we used that \(\varepsilon \le 1/2\). \(\square \)
3 Observations About the Problem Setup
First, it is important to note that a 2-dimensional disk cannot be covered by a curve of bounded length. This is definitely not surprising, but it requires a proof, as the so-called space filling curves [32] can cover a d-dimensional body for \(d\ge 2\).
Lemma 3
For each \(r>0\) and each \(p\in \mathbb R^2\), any curve that passes through each point of the 2-dimensional disk B(p, r) has infinite length.
Proof
(Provided by Swanepoel [34].) Consider a rectangular, regular grid of \(n\times n\) points inside B(p, r) with total side length \(\Theta (r)\); the distance between any two neighbour grid points is \(\Theta (r/n)\). Any curve that goes through those \(n^2\) points has length \(\Theta (rn)\) because the Euclidean minimum spanning tree for those points has length \((n^2-1)\cdot \Theta (r/n)= \Theta (rn)\). Sine n can be chosen arbitrarily large, for any number L, we can find a set of points that cannot be in the image of any path with length L. \(\square \)
This result implies that, without additional information or constraints, a searcher cannot reach a target point \(\mathbb R^d\) for \(d\ge 2\), if it only knows that the target lies inside a ball of positive radius, no matter how small it is.
We say that a c-prediction function \(\lambda \in \Lambda (\varvec{t},c)\) is open if for all \(p\ne \varvec{t}\) we have \(|p\varvec{t}|< \lambda (p) < c\cdot |p\varvec{t}|\). In other words, at each non-target point the prediction is not the correct distance and it is not the maximum possible it could be. This implies that \(\varvec{t}\) lies in the interior of the spherical shell \(S(p,\lambda (p)/c, \lambda (p))\), which is an open set. For example, for \(c>1\) the function \(\lambda (p)=\tfrac{1+c}{2} \cdot |p\varvec{t}|\) is open because \(1< \tfrac{1+c}{2} < c\). Note that the definition is meaningful only for \(c>1\). In the following we show that as long as the target has not been reached, there is a ball around it such that any point in the ball can still be the target: the predictions received at the points visited so far cannot distinguish among the candidate targets in that ball.
Proposition 4
Assume that we have explored a compact set X of points of \(\mathbb R^d\), that the target \(\varvec{t}\) does not belong to X and that the c-prediction \(\lambda \) is open and continuous. There exists an \(\varepsilon >0\) such that the ball \(B(\varvec{t},\varepsilon )\) has the following property: for each \(\varvec{t}'\in B(\varvec{t},\varepsilon )\), there is a c-prediction \(\lambda '\) in \(\Lambda (\varvec{t}',c)\) that is continuous, open and such that \(\lambda '(p)=\lambda (p)\) for all \(p\in X\).
Let us explain the necessity to assume that the prediction is open. This is not because the problem becomes easy otherwise. In general, without this restriction, predictions can still be such that there is an “uncertainty ball” which the target can lie anywhere in. However, it could also happen that for a finite set X of points we have that \(\cap _{p\in X}S(p,\lambda (p)/c,\lambda (p))\) is a single point, which must then be the target \(\varvec{t}\). (This cannot happen when all predictions are open.) In such a case, if the searcher passes through all points of X, they have not reached the target but already have deduced its position. We further assume that X is compact and \(\lambda \) is continuous to avoid that such a deduction can be made when X is infinite.
Proof of Proposition 4
We first provide a simple extension tool. Let S be a sphere and let \(\varvec{t}'\) be a point in the interior of the ball bounded by S. Assume that we have a continuous and open c-prediction \(\lambda :S\rightarrow \mathbb R\) for the potential target \(\varvec{t}'\), but defined only on S. Then there is a continuous and open c-prediction \(\lambda '\) for \(\varvec{t}'\) defined on the whole \(\mathbb R^d\) that extends \(\lambda '\), that is, \(\lambda (p)=\lambda '(p)\) for all \(p\in S\). To show this, we introduce the following notation: for each point \(p\ne \varvec{t}'\), let \(\rho (\varvec{t}',p,S)\) be the unique point where the ray with origin at \(\varvec{t}'\) through p intersects the sphere S. See Fig. 2, left. We then define \(\lambda '(p):=\frac{|p\varvec{t}'|}{|\rho (\varvec{t}',p,S)\varvec{t}'|} \cdot \lambda (\rho (t',p,S))\) for all \(p\in \mathbb R^d\setminus \{ \varvec{t}'\}\), and \(\lambda '(\varvec{t}'):=0\). It is easy to see that \(\lambda '\) is an open c-prediction for \(\varvec{t}'\) because at each ray from \(\varvec{t}'\) it is just a linear function. It is also easy to see that \(\lambda '\) is continuous because \(\lambda \) is continuous. Finally, it is clear from the definition that \(\lambda '\) extends \(\lambda \) because for each \(p\in S\) we have \(p=\rho (\varvec{t}',p,S)\).
We now turn our attention to the main statement. Fix a c-prediction \(\lambda \) for the target \(\varvec{t}\) that is open and continuous. Figure 2, right, may help to follow the notation. Since X is compact and the distance function is continuous, we can define the values
They are both positive because \(\varvec{t}\notin X\), and we have \(X\subseteq S(\varvec{t},A,B)\). Because \(\varvec{t}\notin S(\varvec{t},A,B)\) and \(S(\varvec{t},A,B)\) is compact, we can also define the values
Because \(\lambda \) is open, both values \(\varepsilon '\) and \(\varepsilon ''\) are strictly positive. Let \(\varepsilon =\min \{ \varepsilon ',\varepsilon ''\}/2\), which is also strictly positive. We thus have
We will show that all the points in the ball \(B(\varvec{t},\varepsilon )\) are possible targets. This is natural because each of those points is consistent with the information we got: the disk \(B(\varvec{t},\varepsilon )\) is contained in the spherical shell \(S(p,\lambda (p)/c,\lambda (p))\) for all \(p\in X\) (and actually all \(p\in S(\varvec{t},A,B)\)).
Fix any point \(\varvec{t}'\in B(\varvec{t},\varepsilon )\). Note that for each \(p\in S(\varvec{t},A,B)\) we have
and
Therefore the restriction of \(\lambda \) to the spherical shell \(S(\varvec{t},A,B)\) is also an open and continuous c-prediction for \(\varvec{t}'\).
Let \(S_A\) and \(S_B\) be the inner and outer spheres bounding the spherical shell \(S(\varvec{t},A,B)\), respectively. Let \(\lambda _A\) and \(\lambda _B\) be the restriction of \(\lambda \) to \(S_A\) and \(S_B\), respectively. They are open and continuous because they are a restriction of \(\lambda \).
As discussed at the beginning of the proof, we can extend \(\lambda _A\) to an open and continuous c-prediction \(\lambda '_A\) for the target \(\varvec{t}'\). Similarly, we can extend \(\lambda _B\) to an open and continuous c-prediction \(\lambda '_B\) for the target \(\varvec{t}'\).
Finally, we can define the function \(\lambda '':\mathbb R^d\rightarrow \mathbb R\) by
This function \(\lambda ''\) is continuous because \(\lambda '_A(p)=\lambda (p)\) for all \(p\in S_A\), \(\lambda '_B(p)=\lambda (p)\) for all \(p\in S_B\), and because \(\lambda ,\lambda '_A,\lambda '_B\) are continuous. It is also open and a c-prediction because each of the functions \(\lambda ,\lambda '_A,\lambda '_B\) has these properties. Finally, it is obvious that \(\lambda (p)=\lambda ''(p)\) for all \(p\in X\) because \(X\subseteq S(\varvec{t},A,B)\). \(\square \)
Proposition 4 implies that any search strategy that reaches the target for all c-predictions, where \(c>1\), cannot consist of a finite number of pieces. Indeed, for any c-prediction \(\lambda \) that is open and continuous, until we do not reach the target, there is a ball \(B_\varepsilon \) of radius \(\varepsilon >0\) such that the target may be any point of \(B_\varepsilon \), and the information collected so far cannot distinguish among the possible targets. In particular, an adversary could change from one continuous and open \(\lambda \in \Lambda (\varvec{t},c)\) to another continuous and open \(\lambda '\in \Lambda (\varvec{t}',c)\), for a suitable \(\varvec{t}'\ne \varvec{t}\), at any time before reaching the target because \(\lambda \) and \(\lambda '\) agree on the points that have been explored so far and are indistinguishable. Moreover, any search path needs to have an infinite number of pieces because an adversary can change the target at any time during the search. Finally, knowing that the prediction \(\lambda \) is continuous does not help.
Note also that, because of Lemma 3, we cannot cover all those candidate targets of \(B_\varepsilon \) with a curve of bounded length, unless we collect additional information. This means that we cannot have a search strategy that ignores the prediction \(\lambda \) after some time, because from that moment all points in a ball of positive radius keep being possible targets, and we cannot visit all of them with a curve of bounded length that neglects additional information.
Let us consider for a moment a variant of the model, discussed in Sect. 1.2, where the searcher travels at unit speed and gets the value \(\lambda (p)\) for the current position p at regular time intervals. Since we have argued that the searcher needs to get \(\lambda (p)\) at an infinite number of points p, it follows that in this variant the target cannot be reached within any bounded time. (However, if the target is known to have integer coordinates, this argument does not hold anymore and how to achieve bounded competitive ratio is discussed in Sect. 4.1.)
We return now to our main, continuous model. The following property shows that from the data collected at any given point, we can infer another c-prediction function using the triangular inequality. Moreover, the part that we infer is 1-Lipschitz and thus continuous. The following result is not used in our work, but it may be useful to future research.
Lemma 5
Let \(X\subset \mathbb R^d\) be any non-empty set of points and \(\lambda \) a c-prediction for target \(\varvec{t}\). Then, the function \(\tilde{\lambda }\) defined by
is 1-Lipschitz and the function
is a c-prediction for \(\varvec{t}\).
Proof
The idea is that for any \(p'\in X\), we can replace the prediction at p by \(\min \{|pp'|+\lambda (p'), \lambda (p) \}\), which is something we can deduce because of the triangular inequality.
We first show that the function \(\tilde{\lambda }\) is 1-Lipschitz. Note that \(\min \{ |pp'|+\lambda (p') \mid p'\in X \}\) is not well-defined; the minimum may not exist because we do not assume anything about the prediction function \(\lambda \) or the set X. This is the reason that in the definition of \(\tilde{\lambda }\) we are using the infimum. For each \(\varepsilon >0\) and each \(p\in \mathbb R^d\), there exists a point \(p'_\varepsilon \in X\) such that
Then
Because of symmetry we obtain that
This implies that
and therefore \(\tilde{\lambda }\) is 1-Lipschitz. Note that, in general, \(\tilde{\lambda }\) is not a c-prediction function because, if the target does not belong to X, it is always non-zero.
Next we show that the function \(\mu (p):=\min \{ \lambda (p), \tilde{\lambda }(p)\}\) is a c-prediction for \(\varvec{t}\). For this we use that \(\lambda \) is a c-prediction for \(\varvec{t}\). On the one hand we have
On the other hand
and therefore
This shows that \(\mu (\cdot )\) is a c-prediction for \(\varvec{t}\), as claimed. \(\square \)
The relevance of the result is that at any given point p we get two predictions, \(\lambda (p)\) and the value \(\tilde{\lambda }(p)\) that we can infer. When they are distinct, we can infer more information, which can help the search. However, as we mentioned, we do not exploit this in the strategies we describe.
Finally, we note that the case of \(c=1\) is easy.
Proposition 6
(Case \(c=1\)) For 1-predictions in \(\mathbb R^d\), there is a search strategy with competitive ratio \(1+\varepsilon \) for each \(\varepsilon >0\).
Proof
As usual, we assume that the search starts at the origin \(\varvec{o}\). When \(c=1\), whenever we query for the distance at a point p, we get \(\lambda (p)=|p\varvec{t}|\) and we conclude that the target lies on the \(d-1\) sphere centered at p with radius \(\lambda (p)\). In particular, \(\lambda (\varvec{o})=|\varvec{o}\varvec{t}|\).
We have to find a strategy that reaches the target using a path of length at most \((1+\varepsilon )|\varvec{o}\varvec{t}|=(1+\varepsilon )\lambda (\varvec{o})\). If \(\lambda (\varvec{o})=0\), we are already at the target. We thus assume that \(\lambda (\varvec{o})\ne 0\).
For each of the main orthogonal axis, we move \(\delta =\lambda (\varvec{o})\cdot \varepsilon /(2d)\) along the axis, query the distance to the target, and go back to the origin. The target has to lie in the intersection of the d spheres centered at the points where we queried and also at the sphere centered at the origin. The intersection of these \(d+1\) spheres is always a single point, which must be \(\varvec{t}\); see Fig. 3 for an example for \(d=2\). The uniqueness of the point can be seen for example using the lifting to the paraboloid in \(\mathbb R^{d+1}\) defined by the function \((x_1,\dots ,x_d)\in \mathbb R^d \mapsto \left( x_1,\dots ,x_d, \sum _{i=1}^d (x_i)^2\right) \in \mathbb R^{d+1}\). Each of those spheres corresponds to the intersection of a hyperplane with the paraboloid, and the normals of those \(d+1\) hyperplanes are linearly independent. Therefore, the intersection of those hyperplanes is a single point, which by construction must lie on the paraboloid.
We have walked exactly \((2d)\delta =\varepsilon |\varvec{o}\varvec{t}|\), came back to the origin, and we know now the exact position of the target. Walking to the target takes additional \(|\varvec{o}\varvec{t}|\) length.\(\square \)
4 Upper Bound
In this section, we provide search strategies to reach the target in \(\mathbb R^d\) when we have a c-prediction. First, we provide the key lemma that tells us how to get a sequence of points whose \(\lambda \)-values decreases geometrically. Then, we provide a strategy when the prediction factor is known, followed by a strategy to handle the case for unknown prediction factor. In this setting, we adapt the notation so that \(c^*\) is the true prediction factor, while c is a guess for the true prediction factor. At the end of the section, we discuss some extensions.
Lemma 7
Assume that we are at point \(p_i\) and the prediction factor \(c^*\) is perhaps unknown. Let \(c\ge 1\) be a guess for \(c^*\). Using a search through a path \(\gamma _{i+1}\) of length at most \(2(5c)^d\cdot \lambda (p_i)\) we get to one of the following outcomes:
-
we move from \(p_i\) to a point \(p_{i+1}\) such that \(\lambda (p_{i+1})\le \lambda (p_i)/2\), or
-
we come back to \(p_i\) and correctly deduce that \(c c\), then we have no guaranteed useful bound for \(\lambda (p_*)\).
Our search path will go through the points of N in some order and, at each point of N, we query for the prediction \(\lambda (\cdot )\).
We finish the path as soon as we reach some point \(q_*\in N\) such that \(\lambda (q_*)\le \lambda (p_i)/2\). If for all the points p of N we have \(\lambda (p)> \lambda (p_i)/2\), then we go back to the point \(p_i\). This finishes the general description of the path \(\gamma _{i+1}\).
In the first case, we set \(p_{i+1}=q_*\) and we have moved to a point \(p_{i+1}\) with \(\lambda (p_{i+1})\le \lambda (p_i)/2\). When \(c^*\le c\), we have to be in this case since the point \(p_*\) satisfies the stopping condition \(\lambda (p_*)\le \lambda (p_i)/2\). Thus, if we do not have such a point, we can conclude that \(c^*>c\).
Let’s assume that \(\gamma _{i+1}\) goes through the points of N in arbitrary order. This gives us a simple bound on \(\gamma _{i+1}\)’s length, which has concrete constants and is also easier to use in computations in subsequent theorems.
First, note that any two points in \(B(p_i,\lambda (p_i))\) are at distance at most \(2\lambda (p_i)\). Furthermore, the first edge has length at most \(\lambda (p_i)\) and, if \(\gamma _{i+1}\) comes back to \(p_i\), also the last edge has length at most \(\lambda (p_i)\). Using the bound of Lemma 2 for |N|, we get that the path \(\gamma _{i+1}\) has length at most
Alternatively, it is known [14] that for any set of n points in the d-dimensional ball B(p, r) there is a tour visiting them with length
(Unfortunately, the constant hidden in the term \(O\big ( n^{1-\frac{2}{d}} \big )\) is not given explicitly in [14].) This implies that we can also use a path \(\gamma _{i+1}\) of length \(\lambda (p_i) \cdot O\big ( |N|^{\frac{d-1}{d}}\big ) = O(c^{d-1})\cdot \lambda (p_i)\). With this, the dependency on c is slightly better at the expense of having more ugly-looking constants hidden in the O-notation.
Finally, we note that the whole path \(\gamma _{i+1}\) is contained in \(B(p_i,\lambda (p_i))\), which is contained in \(B(\varvec{t},2\lambda (p_i))\) because \(\varvec{t}\in B(p_i,\lambda (p_i))\). \(\square \)
Theorem 8
(Known prediction factor) Consider the search with predictions problem in \(\mathbb R^d\) where the prediction factor \(c^*>1\) is known. There is a search strategy to reach the target with competitive ratio \(4\cdot 5^d\cdot (c^*)^{d+1}\). The competitive ratio of the strategy can be improved to \(O((c^*)^d)\).
Proof
Let \(p_0=\varvec{o}\) be the starting point and recall that \(\lambda (p_0) \le c^* \cdot |\varvec{o}\varvec{t}|\).
For \(i=0,1,2\dots \) iteratively, we use Lemma 7 with the guessed prediction factor \(c=c^*\) to obtain a path \(\gamma _{i+1}\). As the prediction factor is correct, we always have the outcome in the first item: \(\gamma _{i+1}\) finishes at a point \(p_{i+1}\) with \(\lambda (p_{i+1})\le \lambda (p_i)/2\). It follows by induction that for each \(i\in \mathbb N\cup \{ 0 \}\) we have \(\lambda (p_i)\le \lambda (p_0)/2^i\) and therefore
Let \(\gamma \) be the concatenation of the paths \(\gamma _1,\gamma _2,\dots \). Then
If one uses the alternative bound on \({{\,\textrm{len}\,}}(\gamma _{i+1})\) in Lemma 7, i.e., \({{\,\textrm{len}\,}}(\gamma _{i+1})= O((c^*)^{d-1})\cdot \lambda (p_i)\), a similar calculation to the above gives that \({{\,\textrm{len}\,}}(\gamma ) = O((c^*)^d) \cdot |\varvec{o}\varvec{t}|\).
The path makes an infinite number of straight-line moves. Since for each \(i\in \mathbb N\), the suffix of the path \(\gamma \) after \(p_{i+1}\) is at distance at most \(2\cdot \lambda (p_{i+1}) \le 2 \cdot \lambda (p_0)/2^{i+1}= \lambda (p_0)/2^i\) from \(\varvec{t}\), Lemma 1 implies that \(\varvec{t}\) is the endpoint of the path \(\gamma \). \(\square \)
Theorem 9
(Unknown prediction factor) Consider the search with predictions problem in \(\mathbb R^d\) where the prediction factor \(c^*\) is unknown. There is a search strategy to reach the target with competitive ratio \(6\cdot 10^d \cdot (c^*)^{d+1}\). The competitive ratio of the strategy can be improved to \(O((c^*)^d)\).
Proof
The basic idea is using an exponential search for the constant c. At each step we use Lemma 7 to either move to a point with smaller predicted distance to the target or to detect that our guess for c is too small and double it. Index j parameterizes the current guess \(c=2^j\), and \(p^{(j)}_i\) denotes a point during that guess. At each step we will increase either i or j.
We start setting \(j=1\), \(i=0\) and \(p^{(j)}_i=p^{(1)}_0=\varvec{o}\).
From the current point \(p^{(j)}_i\), we use Lemma 7 with the guessed prediction factor \(c=2^j\) to obtain a path \(\gamma ^{(j)}_{i+1}\). If the outcome is given by the first item of Lemma 7, then we get to a point \(p^{(j)}_{i+1}\) with \(\lambda (p^{(j)}_{i+1})\le \lambda (p^{(j)}_i)/2\); in this case we increase i. If the outcome is given by the second item of Lemma 7, then we get back to \(p^{(j)}_i\); in this case we set \(p^{(j+1)}_i=p^{(j)}_i\), increase j and, from this point on, we will use the new guessed prediction factor \(2^j\), which is twice larger than before. See Fig. 5 for an schematic view of the sequence of points.
Let k be the largest value that index j takes through the procedure. Note that \(k\le \lceil \log _2 c^* \rceil \) since \(2^{\lceil \log _2 c^* \rceil }\) is an overestimate to \(c^*\). If we arrive to \(k= \lceil \log _2 c^* \rceil \), from that point on we will always extend the search path using the outcome in the first item of Lemma 7. Set \(J=\{ 1,\dots , k\}\), which is the set of values that index j takes through the procedure.
For each \(j\in J\), let \(I_j\) be the set of indices i such that the point \(p^{(j)}_i\) is defined and let \(i_j=\max (I_j)\). Note that \(i_k\) is undefined because \(I_k\) is infinite, but \(i_j\) is defined for all \(j0\), there is a suffix of the path such that all the points on the path are at distance \(\varepsilon \) from F. Since the path is continuous and has bounded length, the endpoint of the path has to be at distance 0 from F.
Finally, note that for small d there are tighter bounds on the size of \(\varepsilon \)-nets translating to better constants in our approach. For \(c\approx 1\) one can also exploit that we need an \(\varepsilon \)-net of the spherical shell \(S(\varvec{o},r/c,r)\), which is much smaller than the whole ball \(S(\varvec{o},r)\). However, this improvement is expected to be small since even the \(\varepsilon \)-nets for spheres are not much better.
5 Lower Bound
In this section, we provide a lower bound for the search problem with c-predictions. Our lower bounds are meaningful when we assume that c is large enough, i.e., \(c > 2\). The idea is to construct c-predictions for infinitely many different targets with the property that any two of them are indistinguishable, unless we are quite close to the target. For each such prediction \(\lambda \), there is a small ball around the target where the value of \(\lambda \) is different from the other predictions, but most of the other predictions (except \(\lambda \)) have the same value on that small ball. Then, the searcher has to visit all the small balls around the targets, because in the worst case the target is going to be in the last small ball that is visited.
First, inspired by the technique by Elbassioni, Fishkin and Sitters [13] developed for the Euclidean Traveling Salesperson with Neighbourhoods, one can show the following bound. See Dumitrescu and Tóth [12] for an improvement over [13] where the same idea is reused.
Lemma 10
For any given radius \(\delta \le 1/2\) and dimension \(d\ge 1\), consider the infinite family of balls
Each path in \(\mathbb R^d\) that contains at least one point from each ball of \(\mathbb B\) has length at least \(\left( \big (\frac{1}{2\delta }-1 \big )^d - 1\right) \cdot \delta \cdot \sqrt{\frac{\pi }{d}}\).
Proof
For each \(r\ge 0\), let \(V_d(r)\) denote the volume of the d-dimensional ball of radius r. It is clear that \(V_d(r)=r^d\cdot V_d(1)\).
Consider any path \(\pi \) that touches each ball of \(\mathbb B\) and let L be its length. Consider the volume of the Minkowski sum \(\pi \oplus B(\varvec{o},\delta )\) of the (points on the) path \(\pi \) and the ball \(B(\varvec{o},\delta )\), that is the set of points at distance at most \(\delta \) from \(\pi \). Since the path touches each ball of \(\mathbb B\), the set \(\pi \oplus B(\varvec{o},\delta )\) contains the center of each ball of \(\mathbb B\). This means that \(\pi \oplus B(\varvec{o},\delta )\) contains \(B(\varvec{o},1/2-\delta )\), and therefore we have
On the other hand, for each path \(\pi \) of length L, we have
with equality if and only if \(\pi \) is a straight line. See for example Lemmas 5.1 and 5.2 in [12]. Therefore we get
Using standard formulas for the volume of the d-dimensional ball, one gets that
where we have used the inequality by Kershaw [26]
for \(x=d/2\), which is at least 1 for \(d\ge 2\), and for \(s=1/2\), which gives
(For \(d=1\) we can just check that \(\Gamma (1) = 1 > \frac{\sqrt{\pi }}{2}=\Gamma (3/2)\).) The result follows. \(\square \)
Next, fix a value \(c\ge 2\). For each \(\varvec{t}\in B(\varvec{o},1/2 - 1/c)\), let \(\lambda _{\varvec{t}}\) be the function defined as follows; see Figs. 6 and 7 for intuition.
Lemma 11
Assume that \(c\ge 2\) and \(|\varvec{o}\varvec{t}| \le \tfrac{1}{2}- \tfrac{1}{c}\). Then the function \(\lambda _{\varvec{t}}\) is a c-prediction for the target \(\varvec{t}\). Moreover, for any two distinct \(\varvec{t},\varvec{t}'\) satisfying the hypothesis, the functions \(\lambda _{\varvec{t}}\) and \(\lambda _{\varvec{t}'}\) agree on all points outside \(B(\varvec{t}, 1/c)\cup B(\varvec{t}', 1/c)\).
Proof
Consider any fixed \(\varvec{t}\in B(\varvec{o},1/2- 1/c)\). We have to show that \(\lambda _{\varvec{t}}\) satisfies
We do this by considering points in each part of the domain used to define \(\lambda _{\varvec{t}}\).
The first part is easy as \(|p\varvec{t}| < \lambda _{\varvec{t}}(p) = c \cdot |p\varvec{t}|\) for every \(p\in B(\varvec{t}, 1/c)\). For the second part we note that:
For the last part we first note:
For each \(p\notin B(\varvec{o},1/2)\), let q be the point where the segment \(p\varvec{t}\) crosses the boundary of \(B(\varvec{o},1/2)\). Thus, \(|q\varvec{o}|=1/2\) and, since \(B(\varvec{t},1/c)\subseteq B(\varvec{o},1/2)\), we also have \(|q\varvec{t}|\ge 1/c\). We then have, using that \(c\ge 2\),
This covers all cases for the domain of \(\lambda _{\varvec{t}}\) and concludes the proof that \(\lambda _{\varvec{t}}\) is a c-prediction.
From the definition of \(\lambda _{\varvec{t}}\) it is clear that \(\lambda _{\varvec{t}}(p)=\lambda _{\varvec{t}'}(p)\) for all \(p\notin B(\varvec{t},1/c)\cup B(\varvec{t}',1/c)\) because its value is independent of \(\varvec{t}\) and \(\varvec{t}'\). \(\square \)
Theorem 12
Assume that \(c> 2\). There is family of c-predictions for targets in \(B(\varvec{o},1/2-1/c)\) such that any search path in \(\mathbb R^d\) that uses c-predictions to find the target has length at least \(\left( \frac{c-2}{2}\right) ^d \cdot \frac{1}{c} \cdot \min \{\sqrt{\pi /d},1\}\).
Proof
For each \(\varvec{t}\in B(\varvec{o},1/2 - 1/c)\), consider the function \(\lambda _{\varvec{t}}\) defined in (2). Lemma 11 shows that the function \(\lambda _{\varvec{t}}\) is a c-prediction for each \(\varvec{t}\in B(\varvec{o},1/2 - 1/c)\). Consider the set of prediction functions \(\Lambda = \{ \lambda _{\varvec{t}}\mid \varvec{t}\in B(\varvec{o},1/2 - 1/c)\}\). Let \(\mathbb B=\{ B(\varvec{t},1/c)\mid \varvec{t}\in B(\varvec{o},1/2 - 1/c)\}\). Note that to distinguish between two functions \(\lambda _{\varvec{t}},\lambda _{\varvec{t}'}\in \Lambda \) we have to evaluate them at some point of \(B(\varvec{t},1/c)\cup B(\varvec{t}',1/c)\).
Consider any search strategy when the c-prediction function is selected from \(\Lambda \) by an adversary. The search strategy may exploit that the c-prediction is from \(\Lambda \) and, in particular, it may exploit that the target \(\varvec{t}\) is a point of \(B(\varvec{o},1/2 - 1/c)\), selected by the adversary. We claim that the search path has to visit all the balls of \(\mathbb B\). Indeed, while there are two distinct points \(\varvec{t},\varvec{t}' \in B(\varvec{o},1/2 - 1/c)\) such that the balls \(B(\varvec{t},1/c)\) and \(B(\varvec{t}',1/c)\) are not visited by the search path, we have \(\lambda _{\varvec{t}}(p)=\lambda _{\varvec{t}'}(p)\) for all points p along the path, and therefore the information collected cannot discern whether the target is \(\varvec{t}\) or \(\varvec{t}'\). Thus, in the worst case, the search path has to visit all the balls of \(\mathbb B\) but one, to identify which point of \(B(\varvec{o},1/2 - 1/c)\) is the target, and then still may have to move to that last ball. That is, we may assume that in the worst case the adversary chooses \(\lambda _{\varvec{t}}\in \Lambda \) such that \(B(\varvec{t},1/c)\) is the last ball of \(\mathbb B\) visited by the search strategy. After the searcher deduces at which point of \(B(\varvec{o},1/2 - 1/c)\) the target is, they still have to move to the target.
We conclude that the search path has to visit all balls of \(\mathbb B\), and for the last ball it still has to travel 1/c to the center. Lemma 10 (with \(\delta =1/c\)) implies that the search path has length at least
\(\square \)
For the competitive ratio we have to compare the length of the search path to the distance to the target, which in the construction is at most \(1/2 - 1/c\). We then obtain the following bound, which is non-trivial when \(d\ge 2\) and \(c > 2\).
Corollary 13
Consider the search with predictions problem in \(\mathbb R^d\) with prediction factor \(c>2\). Any search strategy to reach the target has competitive ratio at least \(\left( \frac{c-2}{2}\right) ^{d-1}\cdot \min \{\sqrt{\pi /d},1\}\).
Proof
Consider the construction of Theorem 12. Since the search path has length at least \(\left( \frac{c-2}{2}\right) ^d \cdot \frac{1}{c} \cdot \min \{\sqrt{\pi /d},1\}\) and the target is \(\varvec{t}\in B(\varvec{o},1/2-1/c)\), the competitive ratio is at least
\(\square \)
To get a bound that is easier to grasp, let us assume that \(c\ge 4\). In this case \((c-2)/2\ge c/4\) and we get the following bound.
Corollary 14
Consider the search with predictions problem in \(\mathbb R^d\) with prediction factor \(c\ge 4\). Any search strategy to reach the target has competitive ratio at least \((c/4)^{d-1}\cdot \min \{\sqrt{\pi /d},1\}\).
The lower bounds still hold in the case where the target has integral coordinates or is detected when we are within a given distance, with a slightly worse constant in the basis of the exponential function. For this, we can just scale the input such that the balls in the construction are large enough to contain points with integer coordinates. Then, we still have to visit all balls in order to detect which one has the target.
A similar lower bound holds for randomized search strategies. In our construction, the searcher has to visit some balls in the family \(\mathbb B\) of balls of Lemma 10 (with \(\delta =1/c\)), and they can deduce something only when visiting the ball whose center is the target. In the worst-case (or adversary) model, the target is going to be the center of the last ball of \(\mathbb B\) that is visited. In a randomized setting, we select the target uniformly at random among all the possible ones. This means that \(\varvec{t}\) is selected uniformly at random among the points of \(B(\varvec{o},1/2-1/c)\). The intuition is that, when the search path has touched half of the balls of \(\mathbb B\) (in a measure theoretic sense), with probability 1/2 the ball \(B(\varvec{t},1/c)\) has been touched. We next provide the details.
Lemma 15
Let \(\pi \) be a path in \(\mathbb R^d\) and let p be a point selected uniformly at random in \(B(\varvec{o},1/2-\delta )\), where \(\delta \le 1/2\). If \(\pi \) touches \(B(p,\delta )\) with probability at least 1/2, then \(\pi \) has length at least \(\left( \frac{1}{2}\cdot \big (\frac{1}{2\delta }-1 \big )^d - 1\right) \cdot \delta \cdot \sqrt{\frac{\pi }{d}}\).
Proof
Let L be the length of the path \(\pi \) that touches \(B(p,\delta )\) with probability at least 1/2, when p is selected uniformly at random from \(B(\varvec{o},1/2-\delta )\). The argument used in the proof of Lemma 10 implies the volume inequality
Using the observations and the notation in the proof of Lemma 10, we have
and
Therefore
\(\square \)
Theorem 16
Assume that \(c> 2\). There is family \(\Lambda \) of c-predictions for targets in \(B(\varvec{o},1/2-1/c)\) with the following property. If a prediction is selected uniformly at random from \(\Lambda \), then any search strategy in \(\mathbb R^d\) that uses c-predictions to find the target has, with probability at least 1/2, length at least \(\frac{1}{2}\cdot \left( \frac{c-2}{2}\right) ^d \cdot \frac{1}{c} \cdot \min \{\sqrt{\pi /d},1\}\).
Proof
We adapt the proof of Theorem 12. Consider the family \(\Lambda = \{ \lambda _{\varvec{t}}\mid \varvec{t}\in B(\varvec{o},1/2 - 1/c)\}\) of c-prediction functions and assume that \(\lambda _{\varvec{t}}\) is selected from \(\Lambda \) uniformly at random (by selecting \(\varvec{t}\in B(\varvec{o},1/2 - 1/c)\) uniformly at random).
Let \(\pi \) be the search path followed by the search strategy. Unless \(\pi \) touches \(B(\varvec{t},1/c.)\), it obtains no information about the target. After the searcher hits \(B(\varvec{t},1/c)\) for the first time, it still has to move to the target, which costs an additional 1/c.
Using Lemma 15 with \(\delta =1/c\), we conclude that, with probability at least 1/2, the search path has length at least
\(\square \)
It follows from Theorem 16 that the expected length of the path of any search strategy, randomized or not, is at least \(\frac{1}{4}\cdot \left( \frac{c-2}{2}\right) ^d \cdot \frac{1}{c} \cdot \min \{\sqrt{\pi /d},1\}\). This is 1/4 smaller than the bound in Theorem 12 for worst-case scenarios. We conclude that the lower bounds in Corollaries 13 and 14 hold for randomized strategies, but the lower bound for the expected competitive ratio is worse by a factor of 1/4.
6 Conclusions and Research Directions
We have introduced and studied the problem of searching for a target in \(\mathbb R^d\) under a predictions model in which the searcher is given, at each position they visit, an approximate distance to the target. We presented strategies with competitive ratio of \(O(c^d)\), where c is the prediction factor, which may be unknown. We also showed a lower bound of \((c/4)^{d-1} \cdot \min \{\sqrt{\pi /d},1\}\) for the competitive ratio of any strategy under this model, assuming that \(c\ge 4\), even when the prediction factor c is known.
Let us discuss some of the weaknesses of our techniques to obtain the bounds. Our search strategies use the estimate for the distance to the target only at a finite number of points through the search, but the model permits obtaining the estimate continuously. Thus, we are not exploiting all the properties of the model. Also, our search strategies conduct a search through a sequence of points until it hits a point where the estimate for the distance decreases by 1/2. However, it may be better to stop the iteration over the sequence of points if early on we hit a point where, say, the estimate decreases by 3/4. As for the lower bound, it may be that an adversary that adapts to the search strategy may provide a better lower bound. Our current lower bound largely ignores the search path and just keeps a constant estimate for the distance through most of the search.
It will be interesting to revisit linear search and search in concurrent rays under this paradigm. Here, one can of course use the well-known linear search strategies without predictions, but we expect that predictions throughout the whole search will lead to a better competitive ratio. Previous works [10, 22, 30] where a prediction is only given at the start, already provided a starting ground for this and showed that better search strategies are possible.
The case of \(c=1+\varepsilon \) for sufficiently small \(\varepsilon >0\) seems also interesting, because in this case the spherical shells are very thin, and perhaps one can provide better bounds.
A natural question is how to bring the upper and lower bounds closer. Here, it will be interesting to examine whether randomization can improve the competitive ratios of our strategies, similarly to the case of linear and multiple ray search [17, 24, 25].
Considering the problem in other metric spaces, such as graphs, and searching for more complex targets, such as convex subsets or k-flats, seems also a fruitful line of research. For example, does searching for a k-flat in \(\mathbb R^d\) with predictions behaves like searching for a point in \(\mathbb R^d\) or like a point in \(\mathbb R^{d-k}\)?
One can also study whether weaker assumptions on the prediction function suffice to achieve constant competitive ratio. For example, if the prediction \(\lambda (\cdot )\) satisfies \(|p\varvec{t}|\le \lambda (p)\le 2\cdot |p\varvec{t}|+|p\varvec{t}|^2\) for all \(p\in \mathbb R^d\), can one still achieve constant competitive ratio? In the spirit of [5], can we afford having completely wrong predictions in some region of \(\mathbb R^d\) with non-zero Lebesgue measure, if the region does not contain the target?
Finally, another future line of research is studying the classical geometric variants of pursuit-evasion problems with mobile targets [1, 17] under our predictions model.
Data Availability
No datasets were generated or analysed during the current study.
References
Alpern, S., Gal, S.: The theory of search games and rendezvous, volume 55 of International series in operations research and management science. Kluwer (2003). https://doi.org/10.1007/b100809
Spyros Angelopoulos. Online search with a hint. In Lee, J.R. (ed.) 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 51:1–51:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2021.51 (2021)
Spyros Angelopoulos. Competitive search in the line and the star with predictions. In: Leroux J., Lombardy S., Peleg D. (eds) 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, pages 12:1–12:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.MFCS.2023.12 (2023)
Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. Comput. 106(2), 234–252 (1993). https://doi.org/10.1006/INCO.1993.1054
Banerjee, S., Cohen-Addad, V., Gupta, A., Li, Z.: Graph searching with predictions. In Kalai YT (ed.) 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 12:1–12:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2023.12 (2023)
Beck, A.: On the linear search problem. Israel J. Math. 2, 221–228 (1964). https://doi.org/10.1007/BF02759737
Beck, A., Newman, D.J.: Yet more on the linear search problem. Israel J. Math. 8, 419–429 (1970). https://doi.org/10.1007/BF02798690
Bellman, R.: Minimization problem. Bull. Amer. Math. Soc. 62, 270 (1956)
Bellman, R.: Problem 63–9, an optimal search. SIAM Rev. 5(3), 274–274 (1963)
Bose, P., De Carufel, J.-L., Durocher, S.: Searching on a line: A complete characterization of the optimal solution. Theor. Comput. Sci. 569, 24–42 (2015). https://doi.org/10.1016/J.TCS.2014.12.007
Cabello, S., Giannopoulos, P.: Searching in Euclidean spaces with predictions. In: Bienkowski M, Englert M (eds.) Approximation and Online Algorithms - 22nd International Workshop, WAOA 2024, Egham, UK, September 5-6, 2024, Proceedings, volume 15269 of Lecture Notes in Computer Science, pages 31–45. Springer. https://doi.org/10.1007/978-3-031-81396-2_3 (2024)
Dumitrescu, A., Tóth, C.D.: The traveling salesman problem for lines, balls, and planes. ACM Trans. Algorithms 12(3), 1–29 (2016). https://doi.org/10.1145/2850418
Elbassioni, K.M., Fishkin, A.V., Sitters, R.: Approximation algorithms for the Euclidean traveling salesman problem with discrete and continuous neighborhoods. Int. J. Comput. Geom. Appl. 19(2), 173–193 (2009). https://doi.org/10.1142/S0218195909002897
Few, L.: The shortest path and the shortest road through \(n\) points. Mathematika 2(2), 141–144 (1955). https://doi.org/10.1112/S0025579300000784
Gal, S.: A general search game. Israel J. Math. 12, 32–45 (1972)
Gal, S.: Minimax solutions for linear search problems. SIAM J. Appl. Math. 27(1), 17–30 (1974)
Gal, S.: Search Games. Academic Press, New York (1980)
Subir Kumar Ghosh and Rolf Klein: Online algorithms for searching and exploration in the plane. Comput. Sci. Rev. 4(4), 189–201 (2010). https://doi.org/10.1016/J.COSREV.2010.05.001
Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, October 11-14, 2003, Proceedings, pages 534–543. IEEE Computer Society. https://doi.org/10.1109/SFCS.2003.1238226 (2003)
Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148–1184 (2006). https://doi.org/10.1137/S0097539704446281
Heinonen, J.: Lectures on Analysis on Metric Spaces. Universitext. Springer New York, NY (2001). https://doi.org/10.1007/978-1-4613-0131-8
Hipke, C.A., Icking, C., Klein, R., Langetepe, E.: How to find a point on a line within a fixed distance. Discret. Appl. Math. 93(1), 67–73 (1999). https://doi.org/10.1016/S0166-218X(99)00009-8
Isbell, J.R.: An optimal search pattern. Naval Research Logistics Quarterly 4, 357–359 (1957)
Kao, M.-Y., Ma, Y., Sipser, M., Lisa Yin, Y.: Optimal constructions of hybrid algorithms. J. Algorithms 29(1), 142–164 (1998). https://doi.org/10.1006/JAGM.1998.0959
Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63–79 (1996). https://doi.org/10.1006/INCO.1996.0092
Kershaw, D.: Some extensions of W. Gautschi’s inequalities for the gamma function. Math. Comput. 41(164), 607–611 (1983). https://doi.org/10.2307/2007697
Klein, R.A.: Geometrie: Springer-Verlag (2005). https://doi.org/10.1007/3-540-27619-X (second edition)
Kupavskii, A., Welzl, E.: Lower bounds for searching robots, some faulty. Distributed Comput. 34(4), 229–237 (2021). https://doi.org/10.1007/S00446-019-00358-Y
Langetepe, E.: On the optimality of spiral search. In Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1–12. SIAM. https://doi.org/10.1137/1.9781611973075.1 (2010)
López-Ortiz, A., Schuierer, S.: The ultimate strategy to search on m rays? Theor. Comput. Sci. 261(2), 267–295 (2001). https://doi.org/10.1016/S0304-3975(00)00144-4
Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pages 646–662. Cambridge University Press. https://doi.org/10.1017/9781108637435.037 (2020)
Sagan, H.: Space-filling curves. Springer (1994). https://doi.org/10.1007/978-1-4612-0871-6
Schuierer, S.: On-line searching in simple polygons. In: Christensen, H.I., Bunke, H. and Noltemeier, H. (eds.) Sensor Based Intelligent Robots, International Workshop, Dagstuhl Castle, Germany, September 28 - October 2, 1998, Selected Papers, volume 1724 of Lecture Notes in Computer Science, pages 220–239. Springer. https://doi.org/10.1007/10705474_12 (1998)
Swanepoel, K.: (2023). (Personal communication)
Vaughan, R.C., Wooley, T.D.: The asymptotic formula in Waring’s problem: Higher order expansions. Journal für die reine und angewandte Mathematik (Crelles Journal) 2018(742), 17–46 (2018). https://doi.org/10.1515/crelle-2015-0098
Acknowledgements
The authors would like to thank Kostas Tsakalidis for suggesting the area of algorithmic problems with predictions and Konrad Swanepoel for providing a simple argument for the proof of Lemma 3. We are also grateful to the reviewers for their feedback and suggestions.
Funding
This research was funded in part by the Slovenian Research and Innovation Agency (P1-0297, J1-2452, N1-0218, N1-0285, J1-70045), in part by the Erdős Center, and in part by the European Union (ERC grant KARST, 101071836; ERC grant 882971, GeoScape). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
Author information
Authors and Affiliations
Contributions
Equal contribution by the authors.
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A preliminary version of this work was presented at WAOA 2024 [11].
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/
About this article
Cite this article
Cabello, S., Giannopoulos, P. Searching in Euclidean Spaces with Predictions. Theory Comput Syst 70, 49 (2026). https://doi.org/10.1007/s00224-026-10291-w
Received:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s00224-026-10291-w