The Marco Polo Problem: A Combinatorial Approach to Geometric Localization

(2) University of Rochester); Daniel S. Hirschberg (1); Irvine; Michael T. Goodrich (1); Ofek Gila (1); Shayan Taherijam (1) ((1) University of California; Zahra Hadizadeh (2)

REVIEW 3 major objections 5 minor 31 references

The Marco Polo Problem: A Combinatorial Approach to Geometric Localization

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A searcher with only yes/no distance probes can localize a hidden point in under 2.53 log n questions.

desk verdict Introduces a genuinely new binary-probe localization model with strong algorithmic results, but the lower-bound proof has a real definitional gap and the O(log k) TSP claim is overstated. read the letter →

arxiv 2504.17955 v2 pith:P53XZV7Z submitted 2025-04-24 cs.CG cs.DS

Ofek Gila (1) , Michael T. Goodrich (1) , Zahra Hadizadeh (2) , Daniel S. Hirschberg (1) , Shayan Taherijam (1) ((1) University of California , Irvine , (2) University of Rochester) This is my paper · ORCID

classification cs.CGcs.DS MSC 68U0568Q2590C27

keywords MarcoPoloproblemgeometriclocalizationbinaryprobesprogressiveshrinkingprobecomplexitycomputer-assistedprooftravelingsalespersonsearchandrescue

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces the Marco Polo problem, in which a searcher at the origin may ask only yes/no questions of the form "is there a target within distance $d$ of my current position?" and must get within distance $1$ of a hidden target somewhere in a disk of radius $n$. It claims that this purely combinatorial form of localization is nearly information-theoretically optimal: a carefully chosen, computer-assisted sequence of progressively smaller probes finds a target with fewer than $2.53\lceil\log n\rceil$ questions, while any progressive-shrinking strategy requires at least $2.4\lceil\log n\rceil$ questions. If true, a single constant near $2.5$ binary decisions per halving of the search radius governs this class of search problems. The paper also shows that the probe model can find every one of $k$ targets while traveling only $O(\log k)$ times farther than the optimal tour visiting them, and that the number of times a target device must respond can be capped at any value from $1$ to $\lceil\log n\rceil$ at a predictable probe cost.

What carries the argument

The driving mechanism is the progressive shrinking probe sequence. At each recursion level of radius $r$, probes have radii $\rho_1 r,\rho_2 r,\dots$ with $\rho_k=\rho_1^k$, so each level costs the same number of probes per halving of the radius; balancing the recurrence gives $P(n)\le -\lceil\log n\rceil/\log\rho_1$. The lower bound is the perimeter-covering identity: to force progress, an adversary can keep the target on the perimeter, so probes whose diameters are chords of the search circle must cover the whole circumference, and the optimal chord cover satisfies $\sum_{k\ge1}\sin^{-1}(2^{-k/c})=\pi$, yielding $c\approx 2.40001$. Algorithm 8's machinery is the computer-assisted layout itself: differential evolution for the first six probe centers, then greedy insertion of probes into the largest uncovered convex-hull gap until the disk is covered.

What would settle it

Exhibit a progressive shrinking localization algorithm for circular search areas whose worst-case probe count is certified below $2.40001\lceil\log n\rceil$ for large $n$. Concretely, one could search for a finite per-level probe layout that covers a smaller inscribed disk to recurse on while leaving part of the perimeter unprobed; if such a layout localizes every target with fewer than $2.40001$ probes per halving, the theorem's lower bound is false.

Watch

Extended reading notes

Core claim

Theorem 1 is the load-bearing result: for any progressive shrinking algorithm on a circular search area, $P(n)>2.40001\lceil\log n\rceil$ probes are needed, and Algorithm 8 achieves $P(n)<2.53\lceil\log n\rceil$ probes. The upper bound comes from a per-level layout of 33 probes whose radii shrink geometrically; the first six centers are chosen by differential evolution and the rest are placed greedily into the largest uncovered convex-hull gaps, with the layout certified by computer-assisted proof. The paper further derives $P(n)<3.34\lceil\log n\rceil$ for a monotone spiral path whose worst-case travel is $6.02n$, and a hexagonal-lattice family that trades probes against target responses, giving $P(n)\le 4n^2/3+6n+6$ when a target may respond only once.

Load-bearing premise

The lower bound assumes that every progressive shrinking strategy must cover the entire perimeter of its current search circle, with probe diameters placed as chords of that circle, before it can shrink to a smaller subproblem; if a strategy could instead make progress by recursing on an inner disk while leaving part of the perimeter unprobed, the $2.4\lceil\log n\rceil$ floor would not follow.

Editorial extensions

If this is right

A single target in a radius-$n$ disk can be found with fewer than $2.53\lceil\log n\rceil$ binary probes, within about 5 percent of the $2.4\lceil\log n\rceil$ lower bound for progressive shrinking algorithms.
Directional or range information is unnecessary for near-optimal localization: pure yes/no answers to radial probes suffice.
A monotone spiral path can localize one target while traveling at most $6.02n$, which is less than the $2\pi n$ circumference of the search disk.
Target responses can be capped at any $R_{\max}$ from $1$ to $\lceil\log n\rceil$, with probe cost ranging from $O(n^2)$ at $R_{\max}=1$ down to $6\lceil\log n\rceil$ at $R_{\max}=\lceil\log n\rceil$.
The same memoryless strategy finds all $k$ targets with total distance at most $dn+2dE$, where $E<\mathrm{OPT}(\lceil\log k\rceil+1)$, making the traveled distance $O(\log k)$-competitive with the optimal traveling salesperson tour.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The 2.4-to-2.53 gap suggests the true optimal constant for this probe model lies near 2.5; a lower bound that drops the perimeter-coverage assumption could close the gap.
The computer-assisted layouts point to a general recipe: use global optimization to choose a few large probes, then greedy gap-filling; this could carry over to rectangles, annuli, or higher-dimensional balls, where the perimeter becomes a surface and the constants should shift.
The response-cap family implies a battery-aware protocol: choose $R_{\max}$ from the target device's remaining power and pay the corresponding probe cost, although the paper does not formulate a joint searcher-target energy objective.
The multi-target extension's $O(\log k)$-competitive distance depends on the memoryless re-probing loop; letting the searcher reuse earlier positive probe information might improve the constant, but would break the deliberately stateless design.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing to know: this paper introduces a genuinely new query model and a solid family of algorithms for it. The binary radial probe—yes/no inside a disk, no direction or range—is a natural localization primitive, and the related-work appendix makes a credible case that it hasn't been studied before. The clean recurrence P(n)=k+P(ρ_k n), the progression from hexagonal tilings to chord-based shrinking to the computer-placed darting algorithms (down to 2.53⌈log n⌉ probes), and the response-limited variants are all real contributions. The authors are also unusually honest: Observation 8 admits that their own experiments show probe counts above the worst-case bounds for finite n, with an extra |probes|-2 term, and they flag that constants are asymptotic.

The soft spots are real but mostly addressable. The main one is the lower bound in Theorem 1. Section 2 asserts that any progressive shrinking algorithm must probe the perimeter, then derives the recurrence from 'first success on the kth probe' and takes the new search area to be the kth probe disk. That excludes branches the paper's own algorithms use: the 'omit the last probe' trick recurses on the all-negative region, and more generally, when probe i is first positive, the feasible region is probe_i minus the union of earlier probes, whose covering disk can be much smaller than the probe itself. An algorithm that recursed to that smaller disk could in principle beat 2.40001. The proof needs a formal definition of the algorithm class and a recurrence that covers all-negative and negative-information branches. This is a proof gap, not a demonstrated counterexample, but as written Theorem 1 does not cover the class it claims to bound.

Second, the abstract's O(log k)-competitive multi-target claim outruns the stated theorem. Theorem 5 gives Dtot≤dn+2dE with E

Minor: Algorithm 8's 2.53 constant depends on differential-evolution placement coordinates and greedy fill-in that aren't in the paper; those should be shipped for verification. Observation 8's finite-n caveat should be in the main text, not only the appendix.

Who gets value: computational geometers and search-theory people; it's a good reading-group paper, and I'd likely cite it for the model even while being careful about the lower bound. The paper deserves a serious referee and a major revision rather than a desk reject.

Referee Report

3 major / 5 minor

Summary. The paper introduces the Marco Polo problem, a geometric localization problem in which a mobile search point issues binary 'yes/no' probes (radius-d disks) and must localize one or more stationary points of interest (POIs) within distance n of the origin. The authors propose a series of progressive-shrinking algorithms, from simple hexagonal tiling to computer-assisted 'darting' probe placements, with worst-case probe counts ranging from 5⌈logn⌉ down to 2.53⌈logn⌉. They also prove a lower bound of about 2.4⌈logn⌉ probes for 'progressive shrinking algorithms,' present a family of algorithms trading off probe count against the number of POI responses, and give a memoryless multi-POI extension whose traveled distance is O(log k)-competitive with the optimal TSP tour. The paper includes pseudocode, omitted proofs in an appendix, and large-scale simulations (40 million runs per algorithm).

Significance. If the central lower bound and the advertised upper-bound constants are correct, the paper makes a clean contribution: it defines a natural combinatorial geometric search problem, gives a nearly tight constant-factor characterization (2.4⌈logn⌉ versus 2.53⌈logn⌉), and provides several algorithm families with different trade-offs among probes, traveled distance, and POI responses. The multi-POI extension to an O(log k)-competitive TSP-style tour is also a useful result. Strengths of the manuscript include the breadth of algorithmic ideas, the use of computer-assisted placement with explicit numerical constants, the careful experiments (including Table 1 and Figures 13–15), and the transparent reporting of a discrepancy between theoretical worst-case bounds and observed finite-n performance in Observation 8. The paper is generally well written and the algorithms are described in enough detail to be reproducible.

major comments (3)

[Section 2, 'A Lower Bound for Progressive Shrinking'] The lower-bound argument rests on two unproven assertions: (i) that every progressive shrinking algorithm must probe the entire perimeter of the current search area at each level, and (ii) that after the first positive probe k, the residual uncertainty is exactly the full disk of radius ρ_k n. Neither is established. In particular, the algorithms themselves exploit the all-negative branch: the 'omission of the last probe' optimization recurses to the final unprobed region when all prior probes in a level are negative, and this branch is not modeled by the recurrence P(n)=k+P(ρ_k n). Moreover, when probe i is the first positive probe after i−1 negative responses, the feasible region is probe_i minus the union of the earlier probes, whose minimal enclosing disk can be substantially smaller than the probe disk. An algorithm that recurses to that smaller disk could use fewer probes than P(ρ_i n), potentially lowering the coefficient below 2.40001. The numerical equation Σ sin^{-1}(2^{-k/c}) = π is therefore necessary but not sufficient for the theorem as stated. Theorem 1 should either restrict its scope to a precisely defined memoryless algorithm class that provably excludes these branches, or the lower-bound recurrence must incorporate all-negative and negative-information branches.
[Theorem 1 and Appendix F, Observation 8] The upper-bound constants in Theorem 1 and Figures 4, 6, and 7 (e.g., P(n) < 3.54⌈logn⌉, P(n) < 3.34⌈logn⌉, P(n) < 2.53⌈logn⌉) are stated as if they hold for every n, but Appendix F reports that progressive algorithms can exceed their theoretical worst-case bounds by an additive |probes|−2 term, and Table 1 shows empirical maxima above the stated bounds (e.g., Algorithm 3 max 4.25 versus bound 4.08; Algorithm 8 max 3.20 versus bound 2.53). The paper acknowledges this in Observation 8 and says the bound holds 'for sufficiently large n,' but that caveat is absent from the theorem statement. The claims in Section 2 and in the abstract should be phrased as asymptotic bounds with an explicit n0, or the theorem should state the corrected bound P*(n) = P(n) + |probes| − 2.
[Appendix C, proof of Theorem 6 (Theorem 5 in the main text)] The probe-count bound in the multi-POI theorem uses the inequality Σ_{i=1}^{k−1} ⌈log e_i⌉ ≤ (k−1)⌈log e⌉, justified by 'Jensen's inequality' applied to the concave function log. This justification is invalid as written because the ceiling function is not concave, and Jensen's inequality applies to log, not to ⌈log⌉. The inequality may be true, but it requires a separate proof; for example, one would need to bound the gap introduced by the ceiling operation. As written, the proof of Theorem 5's probe bound is incomplete.

minor comments (5)

[Section 1, first paragraph] The quoted phrase 'Macro' should be 'Marco' in the description of the children's game.
[Section 2, Equation (4)] The typesetting of Equation (4) is garbled; the binomial coefficient is not visually clear. Please reformat it for readability.
[Appendix C, Lemma 1 proof] The formula r = (3L/2 − 1)s is stated for lattices with an even number of layers; the odd-layer case is dismissed in a parenthetical. Please give the explicit odd-layer formula or a short justification.
[Appendix F, Table 1] The table's 'Max' column is useful but should be annotated to indicate that for progressive algorithms the maximum observed value can exceed the displayed theoretical bound because of the last-layer effect discussed in Observation 8.
[General notation] The symbol P(n) is used both for the number of probes in the single-POI problem and for the probability-like notation elsewhere; consider a distinct symbol, e.g., P_1(n), to avoid confusion in Section 3.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all probe-count constants are derived from explicit recurrences and geometric covering conditions, not fitted to data or imported from self-citations.

full rationale

The derivation chain is self-contained. The probe-count bounds are obtained by solving the recurrence P(n)=k+P(rho_k n) under the stated worst-case assumption that the first positive probe is the k-th, then choosing rho_k=rho_1^k so that all k give the same implied constant; this is parameter choice in algorithm design, not fitting to outcome data. The lower bound is derived from the explicit geometric covering condition sum sin^{-1}(2^{-k/c})=pi for probes placed with diameters as chords of the search circle, again with no fitted inputs. The computer-assisted placements in Algorithms 7 and 8 tune free parameters and then greedily place probes, and the resulting probe-count bounds are evaluated from those placements rather than presented as independent empirical predictions. The only self-citations, references [9] and [10], appear as background connections to combinatorial group testing and are not load-bearing for any theorem. The principal caveat is that the lower bound relies on the unproved modeling assertion that any algorithm must probe the perimeter and on a recurrence that does not explicitly cover all-negative branches; that is a proof gap and correctness risk, not circularity, because the paper's own equations do not reduce to themselves or to fitted parameters. No circular step was found.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical entities. Its contributions rest on two kinds of inputs: geometric design constants (ρ1, probe coordinates, layer counts) that are numerically optimized rather than derived from data, and model assumptions about binary probes and adversarial POIs. The perimeter-coverage premise for the lower bound is the most fragile assumption and is flagged.

free parameters (3)

ρ1, first probe proportionality constant = 0.844 (Algorithm 3); 0.74915 (lower bound); other values for Algs 4-8 not printed
The whole progressive-shrinking family sets ρ_k=ρ_1^k; the probe bound is P(n)≤−⌈log n⌉/log ρ_1, so every constant in the results depends on this chosen number.
Probe placement coordinates for Algorithms 4-8 = Determined by differential evolution and greedy gap filling; not published.
The claimed constants 3.54, 3.34, 2.93, 2.53 are only certified for these numerical placements; without the coordinates the bounds cannot be independently audited or reproduced.
Number of probes per recursive layer = 5 (Alg 4), 8 (Alg 5), 11 (Alg 6), 25 (Alg 7), 33 (Alg 8).
These hand or optimizer-selected integers determine both the probe-count bound and the last-layer correction discussed in Observation 8.

assumptions (5)

domain assumption POIs are stationary and placed adversarially anywhere inside a radius-n disk.
All cost bounds are worst-case over POI locations, which is required for the lower bound and for every recursive coverage argument.
domain assumption A probe returns exactly one bit: whether any POI lies within distance d; no direction, distance, or count is revealed.
This is the defining model of the Marco Polo problem, distinguishing it from ranging localization such as Martinson and Dellaert [16].
ad hoc to paper Any progressive shrinking algorithm must cover the entire circumference of the search area at each level.
Entered in Section 2 lower bound: 'any algorithm must at least probe the perimeter of the search area.' The paper does not prove this necessity for all memoryless strategies; it is the load-bearing premise for the 2.40001⌈logn⌉ bound.
standard math The nearest-neighbor heuristic for Euclidean TSP has approximation factor O(log k).
Used in Theorem 5 proof via Rosenkrantz et al. [18], imported as a black box without proof.
domain assumption The probe sequence at each level is a fixed geometric progression ρ_k=ρ_1^k, independent of probe answers.
The analysis and lower bound restrict to progressive shrinking algorithms with a single proportionality constant; adaptive or non-geometric search strategies could evade this parameterization.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Marco Polo Problem: A Combinatorial Approach to Geometric Localization." pith.science (2026). https://pith.science/paper/P53XZV7Z

@misc{pith2026250417955,
  author       = {Pith},
  title        = {Pith review of: The Marco Polo Problem: A Combinatorial Approach to Geometric Localization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P53XZV7Z}},
  note         = {Machine review of arXiv:2504.17955}
}

abstract

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, $\Delta$, that is initially at the origin, a localization algorithm is a strategy to move $\Delta$ 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 $\Delta$ 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 $\Delta$. 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 $\Delta$. 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.

Figures

Figures reproduced from arXiv: 2504.17955 by the authors.

**Figure 1.** An example sequence of probes for an instance of the Marco Polo problem. In this example, the first four probes are negative and the POI (marked with an ✗) is found to within distance 1 on the fifth probe. We also consider generalizations of this problem, such as if there were multiple POIs. One can imagine other applications besides search and rescue for the combinatorial searching problem, including locating is a … view at source ↗

**Figure 2.** If POIs are in one of the two larger probes, [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 2.** Two simple hexagonal algorithms. Algorithm 1 performs probes of radius n/2 along the center of each of the 6 outer hexagons, while Algorithm 2 first performs two radius n/√ 2 probes in the upper two quadrants before performing the remaining probes of Algorithm 1. dk/(1 − ρk). Using this, we determine that: D(n) ≤ max k dk 1 − ρk n. (1) To determine a good bound for this maximum, we use a computer-assisted proof tec… view at source ↗

Figures from the paper (10 more)

**Figure 3.** Figure 3: The optimal placement of progressively decreasing probes of radius proportional to ρ k 1 in order to cover the circumference of the search area. ρ1 must be at least 0.74915 to fully cover the perimeter, as shown. There exists uncovered search area, depicted in blue. Ch…

**Figure 6.** Figure 6: 1 2 3 4 5 6 7 Algorithm 5 P(n) < 3.83⌈log n⌉ D(n) ≤ 6.72n 1 2 3 4 5 6 7 8 9 10 11 Algorithm 6 P(n) < 3.34⌈log n⌉ D(n) ≤ 6.02n [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]

**Figure 5.** Figure 5: A diagram showing the relationship between the k-th circle, centered at Pk, the first circle, centered at O, and the search radius, also centered at O. In particular, we must determine at what position, Pk, to place the center Ck of the k-th probe with radius rk. For s…

**Figure 8.** Figure 8: A hexagonal lattice with L = 4 layers of rings. one such algorithm where L = 2. We describe our family of algorithms by the following routine: 1. Cover the search area with an L-layer lattice. 2. Sequentially probe each hexagon in the lattice until receiving a positive…

**Figure 9.** Figure 9: Algorithm for bounding the distance traveled by ∆. When the POIs are determined to be in the last probe area, ∆ can move directly to the first probe of the next search area, saving distance. If the first probe is at distance d1 from the origin of the original search ar…

**Figure 10.** Figure 10: A search for one POI (✗), first reducing the horizontal dimension to a width of 1 (in the dashed orange probes), then searching along the remaining arc (with the solid blue and orange probes). to find a region of width at most 1 in the first dimension. We then perform…

**Figure 11.** Figure 11: A depiction of the final “simple” search [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]

**Figure 12.** Figure 12: A method to greedily add an arbitrary amount of probes to any initial placement of probes. On the left, Algorithm 4 given an insufficient ρ1 value fails to cover the search area, leaving some uncovered internal area (in blue). On the right, the largest uncovered inter…

**Figure 14.** Figure 14: Simulation results for D/n, where n = 220 . 13 [PITH_FULL_IMAGE:figures/full_fig_p013_14.png]

**Figure 15.** Figure 15: Simulation results for R/⌈log n⌉. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 25 canonical work pages

[1]

The freeze-tag problem: how to wake up a swarm of robots

EstherMArkin,MichaelABender,SándorPFekete, Joseph SB Mitchell, and Martin Skutella. The freeze-tag problem: how to wake up a swarm of robots. Algorithmica, 46:193–221, 2006. doi:10. 1007/s00453-006-1206-1

work page 2006
[2]

Arkin, Michael A

Esther M. Arkin, Michael A. Bender, and Dongdong Ge. Improved approximation algorithms for the freeze-tag problem. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’03, page 295–303, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145/777412.777465. 8

arXiv 2003
[3]

Freeze-Tag in $L_1$ has Wake-up Time Five

Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, and Nicolas Hanusse. Freeze-tag inL_1 has wake-up time five, 2024.arXiv:2402.03258

work page Pith review arXiv 2024
[4]

Euclidean freeze-tag problem on plane

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Saeed Odak. Euclidean freeze-tag problem on plane. In 36th Canadian Conference on Computa- tional Geometry (CCCG), pages 199–205, 2024

work page 2024
[5]

The approximation ratio of the greedy algorithm for the metric traveling salesman problem

Judith Brecklinghaus and Stefan Hougardy. The approximation ratio of the greedy algorithm for the metric traveling salesman problem. Operations Research Letters, 43(3):259–261, 2015. doi:10. 1016/j.orl.2015.02.009

work page 2015
[6]

The detection of defective members of large populations

Robert Dorfman. The detection of defective members of large populations. The Annals of Mathematical Statistics, 14(4):436–440, 1943. URL: http://www.jstor.org/stable/2235930

work page arXiv 1943
[7]

World Scientific, 2nd edition, 2000.doi:10.1142/4252

Ding-Zhu Du and Frank Kwang-Ming Hwang.Com- binatorial Group Testing and Its Applications. World Scientific, 2nd edition, 2000.doi:10.1142/4252

work page doi:10.1142/4252
[8]

Multi-stage group testing improves efficiency of large-scale COVID-19 screening

Jens Niklas Eberhardt, Nikolas Peter Breuckmann, and Christiane Sigrid Eberhardt. Multi-stage group testing improves efficiency of large-scale COVID-19 screening. Journal of Clinical Virology, 128:104382,

work page

Show all 31 references

[9]

Improved combinatorial group testing algorithms for real-world problem sizes

David Eppstein, Michael T Goodrich, and Daniel S Hirschberg. Improved combinatorial group testing algorithms for real-world problem sizes. SIAM Journal on Computing, 36(5):1360–1375, 2007.doi: 10.1137/050631847

2007 doi
[10]

Im- proved adaptive group testing algorithms with appli- cations to multiple access channels and dead sensor diagnosis

Michael T Goodrich and Daniel S Hirschberg. Im- proved adaptive group testing algorithms with appli- cations to multiple access channels and dead sensor diagnosis. Journal of Combinatorial Optimization, 15:95–121, 2008. doi:10.1007/s10878-007-9087-z

2008 doi
[11]

The online freeze-tag problem

Mikael Hammar, Bengt J Nilsson, and Mia Pers- son. The online freeze-tag problem. In LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings 7, pages 569–579. Springer, 2006. doi: 10.1007/11682462_53

2006 doi
[12]

Localization algorithms of wireless sensor networks: a survey.Telecommuni- cation Systems, 52:2419–2436, 2013

Guangjie Han, Huihui Xu, Trung Q Duong, Jinfang Jiang, and Takahiro Hara. Localization algorithms of wireless sensor networks: a survey.Telecommuni- cation Systems, 52:2419–2436, 2013. doi:10.1007/ s11235-011-9564-7

2013
[13]

On the nearest neighbor rule for the metric traveling salesman prob- lem

Stefan Hougardy and Mirko Wilde. On the nearest neighbor rule for the metric traveling salesman prob- lem. Discrete Applied Mathematics, 195:101–103,
[14]

CenWits: a sensor-based loosely coupled search and rescue system using witnesses

Jyh-How Huang, Saqib Amjad, and Shivakant Mishra. CenWits: a sensor-based loosely coupled search and rescue system using witnesses. In 3rd ACM International Conference on Embedded Net- worked Sensor Systems, SenSys ’05, page 180–191,
[15]

The number of circles covering a set

Richard Kershner. The number of circles covering a set. American Journal of Mathematics, 61(3):665– 671, 1939. doi:10.2307/2371320

1939 doi
[16]

Martinson and F

E.B. Martinson and F. Dellaert. Marco Polo localization. In2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422), volume 2, pages 1960–1965, 2003. doi:10.1109/ ROBOT.2003.1241881

1960 arXiv
[17]

Freeze-tag is NP-hard in 3d with L1 distance

Lehilton Lelis Chaves Pedrosa and Lucas de Oliveira Silva. Freeze-tag is NP-hard in 3d with L1 distance. Procedia Computer Science, 223:360– 366, 2023. doi:10.1016/j.procs.2023.08.248

2023 doi
[18]

Rosenkrantz, Richard E

Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis, II. An analysis of several heuristics for the traveling salesman problem.SIAM Journal on Computing, 6(3):563–581, 1977. doi:10.1137/ 0206041

1977
[19]

Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces

Rainer Storn and Kenneth Price. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4):341–359, Dec 1997.doi: 10.1023/A:1008202821328

1997 doi
[20]

Marco Polo (game),

Wikipedia contributors. Marco Polo (game),
[21]

Tag (game) – freeze tag,

Wikipedia contributors. Tag (game) – freeze tag,
[26]

defective

URL: https://en.wikipedia.org/wiki/Tag_ (game)#Freeze_tag. 9 A Additional Related Work As mentioned in the introduction, the Marco Polo prob- lem falls into a rich area of study known aslocalization algorithms; see, e.g., the survey by Han, Xu, Duong, Jiang, and Hara [12]. Our...
[27]

Find an arbitrary POI usingA(n)
[28]

Shut off the tracking device of the found POI
[29]

Without moving∆, re-probe the area at radius 2, 4, 8, etc., until a probe returns a positive result (i.e., another POI is found)
[30]

InvokeA using this new radius to find another POI
[31]

Other than step 1, the performance of the search strategy depends by the relative positions of the POIs

Repeat steps 2 to 4 until all POIs are found. Other than step 1, the performance of the search strategy depends by the relative positions of the POIs. Let the first POI found be POI 0, and the second POI found in step 4 be POI 1. Let the distance between the two POIs be denote...
[2005]

doi:10.1145/1098918.1098938
[2015]

12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2013).doi: 10.1016/j.dam.2014.03.012

2013 doi
[2020]

doi:10.1016/j.jcv.2020.104382

2020
[2025]

URL: https://en.wikipedia.org/wiki/ Marco_Polo_(game)

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

The freeze-tag problem: how to wake up a swarm of robots

EstherMArkin,MichaelABender,SándorPFekete, Joseph SB Mitchell, and Martin Skutella. The freeze-tag problem: how to wake up a swarm of robots. Algorithmica, 46:193–221, 2006. doi:10. 1007/s00453-006-1206-1

work page 2006

[2] [2]

Arkin, Michael A

Esther M. Arkin, Michael A. Bender, and Dongdong Ge. Improved approximation algorithms for the freeze-tag problem. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’03, page 295–303, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145/777412.777465. 8

arXiv 2003

[3] [3]

Freeze-Tag in $L_1$ has Wake-up Time Five

Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, and Nicolas Hanusse. Freeze-tag inL_1 has wake-up time five, 2024.arXiv:2402.03258

work page Pith review arXiv 2024

[4] [4]

Euclidean freeze-tag problem on plane

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Saeed Odak. Euclidean freeze-tag problem on plane. In 36th Canadian Conference on Computa- tional Geometry (CCCG), pages 199–205, 2024

work page 2024

[5] [5]

The approximation ratio of the greedy algorithm for the metric traveling salesman problem

Judith Brecklinghaus and Stefan Hougardy. The approximation ratio of the greedy algorithm for the metric traveling salesman problem. Operations Research Letters, 43(3):259–261, 2015. doi:10. 1016/j.orl.2015.02.009

work page 2015

[6] [6]

The detection of defective members of large populations

Robert Dorfman. The detection of defective members of large populations. The Annals of Mathematical Statistics, 14(4):436–440, 1943. URL: http://www.jstor.org/stable/2235930

work page arXiv 1943

[7] [7]

World Scientific, 2nd edition, 2000.doi:10.1142/4252

Ding-Zhu Du and Frank Kwang-Ming Hwang.Com- binatorial Group Testing and Its Applications. World Scientific, 2nd edition, 2000.doi:10.1142/4252

work page doi:10.1142/4252

[8] [8]

Multi-stage group testing improves efficiency of large-scale COVID-19 screening

Jens Niklas Eberhardt, Nikolas Peter Breuckmann, and Christiane Sigrid Eberhardt. Multi-stage group testing improves efficiency of large-scale COVID-19 screening. Journal of Clinical Virology, 128:104382,

work page