The Marco Polo Problem: A Combinatorial Approach to Geometric Localization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913998000095232 |
|---|---|
| author | Gila, Ofek Goodrich, Michael T. Hadizadeh, Zahra Hirschberg, Daniel S. Taherijam, Shayan |
| author_facet | Gila, Ofek Goodrich, Michael T. Hadizadeh, Zahra Hirschberg, Daniel S. Taherijam, Shayan |
| contents | We introduce and study the Marco Polo problem, which is a combinatorial approach to geometric localization. In this problem, we are told there are one or more points of interest (POIs) within distance $n$ of the origin that we wish to localize. Given a mobile search point, $Δ$, that is initially at the origin, a localization algorithm is a strategy to move $Δ$ to be within a distance of $1$ of a POI. In the combinatorial localization problem we study, the only tool we can use is reminiscent of the children's game, "Marco Polo," in that $Δ$ can issue a probe signal out a specified distance, $d$, and the search algorithm learns whether or not there is a POI within distance $d$ of $Δ$. For example, we could imagine that POIs are one or more hikers lost in a forest and we need to design a search-and-rescue (SAR) strategy to find them using radio signal probes to a response device that hikers carry. Unlike other known localization algorithms, probe responses do not inform our search algorithm of the direction or distance to a POI. The optimization problem is to minimize the number of probes and/or POI responses, as well as possibly minimizing the distance traveled by $Δ$. We describe a number of efficient combinatorial Marco Polo localization strategies and we analyze each one in terms of the size, $n$, of the search domain. Moreover, we derive strong bounds for the constant factors for the search costs for our algorithms, which in some cases involve computer-assisted proofs. We also show how to extend these strategies to find all POIs using a simple, memoryless search algorithm, traveling a distance that is $\mathcal{O}(\log{k})$-competitive with the optimal traveling salesperson (TSP) tour for $k$ POIs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17955 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Marco Polo Problem: A Combinatorial Approach to Geometric Localization Gila, Ofek Goodrich, Michael T. Hadizadeh, Zahra Hirschberg, Daniel S. Taherijam, Shayan Computational Geometry Data Structures and Algorithms I.3.5; F.2.2; I.2.8 We introduce and study the Marco Polo problem, which is a combinatorial approach to geometric localization. In this problem, we are told there are one or more points of interest (POIs) within distance $n$ of the origin that we wish to localize. Given a mobile search point, $Δ$, that is initially at the origin, a localization algorithm is a strategy to move $Δ$ to be within a distance of $1$ of a POI. In the combinatorial localization problem we study, the only tool we can use is reminiscent of the children's game, "Marco Polo," in that $Δ$ can issue a probe signal out a specified distance, $d$, and the search algorithm learns whether or not there is a POI within distance $d$ of $Δ$. For example, we could imagine that POIs are one or more hikers lost in a forest and we need to design a search-and-rescue (SAR) strategy to find them using radio signal probes to a response device that hikers carry. Unlike other known localization algorithms, probe responses do not inform our search algorithm of the direction or distance to a POI. The optimization problem is to minimize the number of probes and/or POI responses, as well as possibly minimizing the distance traveled by $Δ$. We describe a number of efficient combinatorial Marco Polo localization strategies and we analyze each one in terms of the size, $n$, of the search domain. Moreover, we derive strong bounds for the constant factors for the search costs for our algorithms, which in some cases involve computer-assisted proofs. We also show how to extend these strategies to find all POIs using a simple, memoryless search algorithm, traveling a distance that is $\mathcal{O}(\log{k})$-competitive with the optimal traveling salesperson (TSP) tour for $k$ POIs. |
| title | The Marco Polo Problem: A Combinatorial Approach to Geometric Localization |
| topic | Computational Geometry Data Structures and Algorithms I.3.5; F.2.2; I.2.8 |
| url | https://arxiv.org/abs/2504.17955 |