CS Paper Radar

Two-Dimensional Search for a Moving Target on Rectangular and Cylindrical Grids

Alexey Lebedev, Vladimir Lebedev, Christian Deppe

cs.DM ·submitted 2026-10-31 21:27 UTC · v1

Abstract

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$.

Closest papers

Nearest neighbours by meaning across the whole index.

Bellman Search in Arbitrary Finite Dimension: A Self-Similar Cell Theorem and Effective Computability of Planar Shoreline Search

cs.CG math.MGmath.OC ·2026-08-29 ·Florentin Koch
theory similarity 0.61
Abstract · 23 pages, 1 figure. English revision 8.3

A shoreline-search path starts at the origin and must meet an unknown affine line, without knowing either its normal or its distance. We first establish a self-similar reduction theorem for homogeneous search problems whose historical information is a record profile updated by pointwise maximum. Two quasi-returns of the normalized state delimit a block that renews the required profile by itself; a short connector closes this block into a cell. Every finite-ratio path can therefore be approximated, with arbitrarily small loss, by repetitions of a single cell at all scales. The main chain is then made effective. A finite coding of the state space computably bounds the scale factor and normalized length of a nearly optimal cell. For planar Shoreline search, the support function of the convex hull gives an exact cell functional. A one-sided polygonalization then reduces the problem to a computable number of vertices, after which quantifier elimination decides whether a polygonal cell exists below a rational threshold. It follows that the optimal deterministic planar Shoreline value $C_2^*$ is a computable real: for every rational $ε>0$, an algorithm terminates with a rational interval of width at most $ε$ containing $C_2^*$. Additional results---sliding memory, Bellman transitions, deadlines, geometric filters, and relative equilibria---are presented separately as a toolbox for certified computation and for the study of spiral rigidity; they are not used in the computability proof.

0.61

Strategic Facility Location in Euclidean Spaces

cs.GT cs.DS ·2026-09-04 ·Kim Thang Nguyen, Lucas Perotin, Bertrand Simon
similarity 0.54
Abstract

The strategic facility location problem is defined as follows: $n$ agents report their location in a metric space, and the objective is to design a \emph{mechanism} deciding the (possibly randomized) location of a facility such that agents have no incentive to lie about their position. We focus on the egalitarian cost, which means that the goal of the mechanism is to minimize the expected maximal facility-agent distance. Meanwhile, mechanisms must be \emph{truthful} (or \emph{strategyproof}): no agent may decrease their expected distance to the facility via lying on their location. Designing truthful mechanisms minimizing the approximation ratio is a well-studied problem, and the optimal solution is known for the real line. We focus in this paper on higher dimension Euclidean spaces, for which gaps remain between the best known lower and upper bounds. We first show that, maybe counter-intuitively, the problem is easier for two agents on the plane rather than on the line: the mechanism can exploit the additional dimension to prevent more efficiently agent lies. Based on this intuition, we devise lower bounds for $\mathbb R^d$ asymptotically matching the best known approximation factor of $2$ for large $d$. We also provide novel mechanism ideas, improving over the best known algorithms on the plane, and when the agents belong to $\mathbb R^d$ but the facility may use an additional dimension.

0.03

Optimality and Impossibility in Multidimensional Strategyproof Facility Location

cs.GT ·2026-10-27 ·Jianan Lin
theory similarity 0.54
Abstract

We study facility location in multidimensional normed spaces with the objective of minimizing social cost, the sum of agents' distances to their nearest facility. A deterministic mechanism selects $k$ facility locations based on the reports of $n$ agents and is strategyproof (SP) if no agent can reduce her distance by misreporting her location. We establish optimal approximation ratios and impossibility results. For a single facility in the Euclidean plane, we prove that the optimal approximation ratios among deterministic SP mechanisms are exactly those obtained by Goel and Hann-Caruthers [SCW 2023] for the coordinate-wise median (CM): $\frac{\sqrt{2(n^2+1)}}{n+1}$ for odd $n\ge3$ and $\sqrt{2}$ for even $n\ge4$. We remove the anonymity assumption from their optimality result. However, CM is not always optimal in non-Euclidean spaces: we give an SP mechanism that minimizes social cost exactly in $\ell_\infty^d$, whereas CM has a tight uniform approximation ratio of $2$ already in the plane. We then consider two facilities in $\ell_p$ spaces with $1<p<\infty$ and prove two impossibility results for every $n>2$. In the plane, no deterministic SP mechanism has a finite approximation ratio. In higher dimensions, the same impossibility holds for anonymous deterministic SP mechanisms. Finally, a reduction using distant agents and a limiting argument extends both impossibility results to every $k>2$ with $n>k$.

0.17

Learning-Augmented Strategyproof Facility Location in $\mathbb{R}^d$ with $\ell_p$ Distances

cs.GT ·2026-09-11 ·Hau Chan, Jianan Lin, Chenhao Wang
similarity 0.53
Abstract

We study learning-augmented mechanism design for locating a single facility in $\mathbb{R}^d$ to minimize the sum of the agents' $\ell_p$ distances to the facility. We analyze the coordinate-wise median with predictions (CMP) mechanism, which adds $cn$ virtual agents at a predicted optimal facility location to the $n$ reported locations and returns their coordinate-wise median. The parameter $c\in[0,1)$ represents confidence in the prediction; CMP is known to be strategyproof when both are fixed independently of the reports. We determine its approximation guarantees under correct predictions (consistency) and arbitrary predictions (robustness) in two settings. First, for $d=2$, we establish exact guarantees for every $p\in[1,+\infty]$. For $1<p<+\infty$, the consistency and robustness are respectively $\Bigl(1+\bigl(\frac{1-c}{1+c}\bigr)^{\frac{p}{p-1}}\Bigr)^{\frac{p-1}{p}}$ and $\Bigl(1+\bigl(\frac{1+c}{1-c}\bigr)^{\frac{p}{p-1}}\Bigr)^{\frac{p-1}{p}}$. We use the median condition in each coordinate to compare the mechanism's cost with the optimal cost, and establish tightness using instances with agents at only three distinct locations. Second, for $1<p<+\infty$, we obtain dimension-independent consistency and robustness upper bounds valid for every $d\ge1$. For each fixed $p$ and $c$, we construct families of instances whose ratios approach the respective upper bounds as $d\to\infty$, proving asymptotic tightness. We also establish exact guarantees for $p=1$ in every dimension and asymptotically tight bounds for $p=+\infty$. Our high-dimensional results recover the prediction-free bounds of Gravin and Jia (STOC 2025) when $c=0$ and their learning-augmented bounds in arbitrary-dimensional Euclidean spaces when $p=2$.

0.07

Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs

cs.DM math.PRmath.CO ·2026-09-11 ·Dávid Ferenczi, Alexander Grigoriev
theory similarity 0.53
Abstract · 18 pages, 1 figure

Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed $δ\in (0,1)$, there exists $C_δ>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-δ)n$ in $G(n,p)$ with high probability whenever $p\ge C_δ\sqrt{\ln k/n}$. Thus, for $k^2=Θ(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.

0.15

Positioning a Movable Antenna Without CSI: A Kernelized Bandit Under Costly Movement

eess.SP ·2026-09-23 ·Wonseok Choi, Yunseob Tae, Jeongjae Lee, Songnam Hong
theory similarity 0.53
Abstract · Submitted to IEEE Transactions on Wireless Communications

Movable antenna (MA) systems reconfigure the wireless channel by repositioning the antenna within a confined region. The position optimization behind this capability has been studied under the premise that the channel at every candidate position is known. However, acquiring that knowledge is costly: a position can be measured only after the antenna has moved there, which takes many slots at the speed of the actuator, and the channel drifts meanwhile. We formulate MA positioning as a non-stationary kernelized bandit with a reachability constraint, in which exploration, tracking, and the reward lost in transit are coupled through a single physical action. We propose MoveUCB, which addresses the reachability constraint through a global target search, a persistence rule that holds the target across slots, and a transit-aware movement cost term. We prove that MoveUCB attains sublinear dynamic regret under the standard variation-budget condition of non-stationary bandits alone, with the physical parameters entering only through constants. Simulations against a dynamic-programming oracle and movement-unaware baselines show that MoveUCB attains the lowest regret with about half the travel of the closest baseline that moves.

0.49

Infinite Worlds from One Example: What Local Generators Must Share

cs.LG cs.GR ·2026-10-31 ·Amin Najafgholizadeh, Mohsen Afsharchi
similarity 0.53
Abstract · 85 pages, 12 figures, 48 tables. v2: supplementary file merged into the main PDF as appendices; corrections in the appendices

Seeded noise lets games generate any region of an unbounded world on demand. We ask what such a generator needs when every small window must come from one example, the constraint behind Wave Function Collapse. The difficulty is that local constraints can require agreement over arbitrary distances: in a brick wall, each row keeps its place between the mortar lines. We study local generators, each cell a fixed function of the randomness near it. When the constraints carry a quantity that varies across the example, no generator that applies one rule, ignoring position, to independent randomness at every cell can be both exactly valid and faithful to the example's statistics, however far each cell reads. At radius r, staying faithful forces forbidden windows at a density of at least order 1/r, and a construction attains this order. To vary the quantity between exactly valid worlds, a generator needs randomness shared along its direction. We give a finitely checkable condition under which row types drawn from the seed and the position modulo a fixed period suffice for exact validity without learning. A search over the example's patches certifies these quantities and names the input each needs. Across 52 public examples of Wave Function Collapse and 27 from other implementations, it certifies only examples where a learned generator on independent randomness stays far from valid after repair. Given that input, a neural cellular automaton and a diffusion model become valid on 10 and 8 of the 12 certified examples that receive one, and on none from independent randomness. Valid means at most one forbidden window in a thousand after repair. With octaves of seeded noise elsewhere, the automaton is valid on 45 of the 52 public examples and 21 of the 27 from other implementations, and repair keeps random access.

0.30

Mechanism Design for Facility Location Games Under a Prelocated Facility

cs.GT ·2026-08-31 ·Genjie Qin, Qizhi Fang, Wenjing Liu
publishedtheory similarity 0.52
Abstract

We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of $n$ agents is located on a real line or a circle, each of whom has her location as private information, and her cost is the (expected) distance from her location to the nearest facility. Our goal is to design mechanisms which can approximately minimize the maximum cost or the social cost while eliciting agents' private information truthfully (i.e., strategy-proof). Based on real-life scenarios, we consider the problem in two settings: the general setting where each agent can be located at both sides of the prelocated facility, and the special setting where all the agents are located at the same side of the prelocated facility. For agents on a line, in the general setting, we design the best possible deterministic strategy-proof mechanism with $2$-approximation and provide a lower bound of $1.5-ε\textbf{ }(ε>0)$ for any randomized strategy-proof mechanism under the maximum cost objective. For the social cost, we obtain an upper bound of $n$ for deterministic strategy-proof mechanisms and lower bounds of $1.5$ and $1.0425$ for any deterministic strategy-proof mechanism and any randomized strategy-proof mechanism, respectively. In the special setting, we further provide a randomized strategy-proof $5/3$-approximation mechanism for the maximum cost and a deterministic strategy-proof $(n-1)$-approximation mechanism for the social cost. For agents on a circle, we provide a deterministic strategy-proof 2-approximation mechanism under the maximum cost objective.

0.39