The Rectilinear Marco Polo Problem
Ofek Gila, Michael T. Goodrich, Zahra Hadizadeh, Daniel S. Hirschberg, Shayan Taherijam · 2025
Read The Rectilinear Marco Polo Problem by Ofek Gila, Michael T. Goodrich, Zahra Hadizadeh, Daniel S. Hirschberg, Shayan Taherijam (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14820.txt.
Introduction
Ofek Gila, Michael Goodrich, Zahra Hadizadeh, Daniel Hirschberg, and Shayan Taherijam study a search problem inspired by the Marco Polo game, in a 2025 paper. A hidden point of interest lies within a known distance of the start. A searcher moves through the space and may send out probes; a probe only reports whether the target is within a stated range, never where it is. The setting here uses grid-like distances suited to city streets, and extends to higher dimensions.
The goals are to use few probes and travel little distance before landing near the target. The authors describe several efficient search strategies for this rectilinear version. The work is motivated by search and rescue, where a team must find a beacon with only rough range answers to guide it.
Catalog record
| CREATOR | Ofek Gila, Michael T. Goodrich, Zahra Hadizadeh, Daniel S. Hirschberg, Shayan Taherijam |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-14820
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Rectilinear Marco Polo Problem Thanks: This research was supported in part by NSF grant 2212129. Ofek Gila, Michael T. Goodrich, Zahra Hadizadeh, Daniel S. Hirschberg, Shayan Taherijam Abstract We study the rectilinear Marco Polo problem , which generalizes the Euclidean version of the Marco Polo problem for performing geometric localization to rectilinear search environments, such as in geometries motivated from urban settings, and to higher dimensions. In the rectilinear Marco Polo problem, there is at least one point of interest (POI) within distance n n , in either the L 1 L_{1} or L ∞ L_{\infty} metric, from the origin. Motivated from a search-and-rescue application, our goal is to move a search point , Δ \Delta , from the origin to a location within distance 1 1 of a POI. We periodically issue probes from Δ \Delta out a given distance (in either the L 1 L_{1} or L ∞ L_{\infty} metric) and if a POI is within the specified distance of Δ \Delta , then we learn this (but no other location information). Optimization goals are to minimize the number of probes and the distance traveled by Δ \Delta . We describe a number of efficient search strategies for rectilinear Marco Polo problems and we analyze each one in terms of the size, n n , of the search domain, as defined by the maximum distance to a POI. 1 Introduction Gila, Goodrich, Hadizadeh, Hirschberg, and Taherijam [ 13 ] introduce the Marco Polo problem, which they motivate in terms of one or more points of interest (POIs), thought of as hikers lost in a forest, that we would like to localize using a mobile search point, \Delta . Each lost hiker is assumed to have a wireless device that can respond to probes sent from \Delta to a specified distance such that if a lost hiker is within that distance of \Delta , then the search algorithm will receive a positive response. Such probes use up power, of course, both for \Delta and for a POI’s tracking device; hence, the goal is to devise a search algorithm for \Delta and a sequence of probes that minimizes the number of probes needed to locate a POI to within a distance of 1. In the formulation of Gila et al. [ 13 ] , the underlying geometry for the Marco Polo problem is Euclidean, such that \Delta can move unrestrictedly in any direction and probes are circles, which seems reasonable for searching in a forest but not for searching in an urban environment where distance is more accurately abstracted as being rectilinear. In this paper, we are interested in studying a rectilinear version of the Marco Polo problem. As a colorful motivation of the two-dimensional version of the rectilinear Marco Polo problem, suppose one or more people have been kidnapped and are being held in one or more secret points of interest (POIs) in a city (like New York, Chicago, or Toronto) whose streets are essentially grids. A mobile search point, \Delta , can move to search for them that is restricted to flying or driving along rectilinear paths (since it cannot fly or drive through buildings). Each kidnap victim at a POI has a hidden electronic device that can respond to probes from \Delta , which can issue probes to specified rectilinear distances such that if there is a kidnap victim within this distance, then our search algorithm will learn this. But the search algorithm does not learn the direction or distance to the kidnap victim. The optimization problem is to minimize the number of probes and/or victim responses, as well as possibly minimizing the travel distance for \Delta . We are therefore interested in efficient searching strategies for rectilinear Marco Polo problems with analyses in terms of the size, n , of the search domain. We can therefore formulate the rectilinear Marco Polo problem as a computational geometry problem, where we have at least one point of interest (POI) at distance at most n from the origin, and we want to move a search point , \Delta , to within distance 1 of a POI, guided by probes. A probe is a query specified by \Delta ’s position and a distance, d , such that we learn whether or not a POI is within distance d from \Delta , in either the L_{1} or L_{\infty} metric. Our optimization goals are to minimize the number of probes and distance for \Delta to travel to find a POI. Related Prior Work. We are not familiar with any prior work on the rectilinear Marco Polo problem. As mentioned above, Gila, Goodrich, Hadizadeh, Hirschberg, and Taherijam [ 13 ] introduce the Euclidean version of the Marco Polo problem, where search paths are not restricted and travel distances and probe distances are measured with the Euclidean L_{2} metric. For example, they provide a number of carefully choreographed travel patterns and probe strategies, including one that finds a POI with 3.34\lceil\log n\rceil probes and flight distance 6.02n and a strategy that uses 2.53\lceil\log n\rceil probes and flight distance 45.4n . The Marco Polo problem is related to combinatorial group testing, see, e.g., [ 9 , 11 , 14 , 8 , 10 ] . In this problem, one is given a set of n items, at most d of which are “defective.” Subsets of the items can be pooled and tested as a group, such that if one of the items in the pool is defective, then the test for the pool will be positive. Tests can be organized either adaptively or non-adaptively to efficiently identify the defective items based on the outcomes of the tests. The Marco Polo problem differs from combinatorial group testing, however, in that the search space for the Marco Polo problem is a geometric region and tests must be connected geometric shapes (like squares), whereas the search space in combinatorial group testing is for a discrete set of n items and tests can be arbitrary subsets. Another related problem in computational geometry is the freeze tag problem [ 2 , 15 , 3 , 7 ] , which has also been studied in the rectilinear setting [ 6 , 19 ] , where one is interested in moving robot points in the plane to “wake up” a collection of robots. Also, another related rectilinear combinatorial optimization problem is the optimization problem abstracted from the Minesweeper game; see, e.g., [ 17 ] . There is also considerable prior work on search-and-rescue algorithms focused on non-combinatorial solutions, including the use of continuous monitoring, sophisticated cameras, and non-adaptive travel patterns; see, e.g., [ 1 , 5 , 18 , 20 , 22 , 21 , 16 , 4 ] . Problem definition. In the rectilinear Marco Polo problem, there are k\geq 1 entities, which we’ll call points of interest (POIs), with unknown positions, at least one of which are within a distance, n , in the L_{1} or L_{\infty} distance metric, of a point, O , called the origin . That is, the search region is a diamond or square in \mathbb{R}^{2} or a octahedron or cube in \mathbb{R}^{3} . A probe , p(x,y,d) , is a query that asks if