← 研踪 PaperTrailarXiv:2611.01281 · v1
Two-Dimensional Search for a Moving Target on Rectangular and Cylindrical Grids
首次提交 2026-11-01 05:27
版本更新 2026-11-01 05:27
雷达观测 2026-11-04 23:43
摘要
We study how precisely a moving target can be localized on finite rectangular grids and their cylindrical counterparts. Each query asks whether the target lies in a chosen subset of vertices and receives a noiseless answer. Queries may depend on previous answers. Between successive queries, the target may stay in place or move along one horizontal or vertical edge. Accuracy is measured by the number of positions still possible immediately after the final answer, with no subsequent movement. A strategy achieves accuracy $s$ if it always terminates with at most $s$ possible positions, whatever admissible trajectory the target follows. Thus $s=1$ means exact localization. We denote by $s^*(M,N)$ the smallest value of $s$ achievable by a finite adaptive strategy on a finite grid. Our main result shows that every finite rectangular grid admits a strategy that localizes the target to at most eight positions, regardless of the grid dimensions: $s^*(M,N)\leq8$. The construction uses nine local query patterns and their vertical reflections. Its termination follows from the progress these patterns force toward the finite grid boundaries. We also prove the dimension-dependent bound $s^*(M,N)\leq\min\{M+1,N+1\}$. For finite cylindrical grids $P_M\square C_N$, where the columns are periodic but the first and last rows remain boundaries, we introduce the corresponding accuracy parameter and state the proposed dimension-independent bound $s^*_{\mathrm{cyl}}(M,N)\leq9$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-01 05:27 · 最新观测版本
Two-Dimensional Search for a Moving Target on Rectangular and Cylindrical Grids
We study how precisely a moving target can be localized on finite rectangular grids and their cylindrical counterparts. Each query asks whether the target lies in a chosen subset of vertices and receives a noiseless answer. Queries may depend on previous answers. Between successive queries, the target may stay in place or move along one horizontal or vertical edge. Accuracy is measured by the number of positions still possible immediately after the final answer, with no subsequent movement. A strategy achieves accuracy $s$ if it always terminates with at most $s$ possible positions, whatever admissible trajectory the target follows. Thus $s=1$ means exact localization. We denote by $s^*(M,N)$ the smallest value of $s$ achievable by a finite adaptive strategy on a finite grid. Our main result shows that every finite rectangular grid admits a strategy that localizes the target to at most eight positions, regardless of the grid dimensions: $s^*(M,N)\leq8$. The construction uses nine local query patterns and their vertical reflections. Its termination follows from the progress these patterns force toward the finite grid boundaries. We also prove the dimension-dependent bound $s^*(M,N)\leq\min\{M+1,N+1\}$. For finite cylindrical grids $P_M\square C_N$, where the columns are periodic but the first and last rows remain boundaries, we introduce the corresponding accuracy parameter and state the proposed dimension-independent bound $s^*_{\mathrm{cyl}}(M,N)\leq9$.
查看此版本解读 →查看此版本原文 ↗