The Rectilinear Marco Polo Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908496445833216 |
|---|---|
| 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 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$, in either the $L_1$ or $L_\infty$ metric, from the origin. Motivated from a search-and-rescue application, our goal is to move a search point, $Δ$, from the origin to a location within distance $1$ of a POI. We periodically issue probes from $Δ$ out a given distance (in either the $L_1$ or $L_\infty$ metric) and if a POI is within the specified distance of $Δ$, then we learn this (but no other location information). Optimization goals are to minimize the number of probes and the distance traveled by $Δ$. We describe a number of efficient search strategies for rectilinear Marco Polo problems and we analyze each one in terms of the size, $n$, of the search domain, as defined by the maximum distance to a POI. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14820 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Rectilinear Marco Polo Problem Gila, Ofek Goodrich, Michael T. Hadizadeh, Zahra Hirschberg, Daniel S. Taherijam, Shayan Computational Geometry I.3.5; F.2.2; I.2.8 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$, in either the $L_1$ or $L_\infty$ metric, from the origin. Motivated from a search-and-rescue application, our goal is to move a search point, $Δ$, from the origin to a location within distance $1$ of a POI. We periodically issue probes from $Δ$ out a given distance (in either the $L_1$ or $L_\infty$ metric) and if a POI is within the specified distance of $Δ$, then we learn this (but no other location information). Optimization goals are to minimize the number of probes and the distance traveled by $Δ$. We describe a number of efficient search strategies for rectilinear Marco Polo problems and we analyze each one in terms of the size, $n$, of the search domain, as defined by the maximum distance to a POI. |
| title | The Rectilinear Marco Polo Problem |
| topic | Computational Geometry I.3.5; F.2.2; I.2.8 |
| url | https://arxiv.org/abs/2508.14820 |