Pith. sign in

REVIEW 3 major objections 3 minor 61 references

Disk and Partial Disk Inspection: Worst- to Average-Case and Pareto Upper Bounds

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

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

Pith's one-line read The authors prove new upper bounds for the average time to inspect a unit disk's perimeter with n mobile agents, beating 1961 heuristics and giving the first Pareto trade-off curve.

desk verdict Real progress on a classic problem, but the flagship methodological claim outruns the proof; the worst-case theorem and corrected numerical work stand on their own. read the letter →

arxiv 2411.15391 v4 pith:64MPCOVI submitted 2024-11-23 cs.DM cs.CG

James Conley , Konstantinos Georgiou This is my paper · ORCID
classification cs.DMcs.CG MSC 90B4068W40
keywords diskinspectionshorelineproblemmobileagentsaverage-caseanalysisworst-caseParetoupperboundsnonlinearprogrammingsearchtheory
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 studies n unit-speed agents that start at the center of a unit disk and must inspect the entire perimeter, where a point is considered seen only when an agent is outside the disk with unobstructed line of sight. For the worst case, it solves the partial-inspection problem of covering an arc of length c, which yields, as a corollary, a single proof of the optimal worst-case times for any number of agents. For the average case, it introduces a systematic method: discretize the perimeter, solve a nonlinear program for a polygonal trajectory whose vertices lie on tangent lines, then translate the discrete solution back to a feasible continuous trajectory with at most a $(1+1/k)$ cost blow-up. This improves the 1961 average-case heuristics of Gluss (which the paper shows contained numerical errors) to $3.5509015$ for one agent, $1.7946051$ for two agents, and $\frac{n}{2\pi}\log\frac{1+\sin(\pi/n)}{1-\sin(\pi/n)}$ for $n\ge 3$, with the average asymptotically approaching $1+\frac{\pi^2}{6n^2}$. The same machinery produces Pareto upper bounds for trading worst-case against average-case performance in the single-agent problem.

What carries the argument

The central object is the ExtendedPolySegment (EPS) trajectory: the agent first moves from the disk center to a deployment point $A_0=(1,\tan\theta)$ and then travels a polygonal chain whose $k$ vertices $A_i$ lie on the tangent lines $L_i$ to the disk at the sampled perimeter points. The load-bearing identity is the lift in Lemma 4, which shows that when the tangent parameters satisfy $t_i \ge \frac{1-\cos((c-2\theta)/k)}{\sin((c-2\theta)/k)}$, each segment $A_{i-1}\to A_i$ inspects all perimeter points between the two tangent contacts, so the discrete trajectory is feasible for the continuous problem and its average cost is at most $(1+1/k)$ times the discrete average. This lift converts numerical NLP solutions into provable continuous upper bounds, and the same family of trajectories, optimized with objective $\lambda\cdot\text{worst}+(1-\lambda)\cdot\text{average}$, gives the Pareto trade-off curve.

What would settle it

Solve the continuous single-agent average-case problem independently, for instance with the Fermat-principle/ODE reduction cited in the paper's discussion, and check whether the optimal trajectory touches the disk anywhere. If it does, the discretization guarantee collapses; if it does not, the guarantee holds and the reported bound should converge to the true optimum (about 3.549259) as $k$ grows.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the continuous disk-inspection problem can be attacked through a discrete auxiliary problem with a rigorous one-way lift: any feasible discrete inspection trajectory built as a polygonal chain with vertices on the tangent lines at sampled perimeter points is also feasible for the continuous problem, and its average cost is at most $(1+1/k)$ times the discrete average. Optimizing such chains with a nonlinear program yields explicit trajectories that beat all previously reported average-case upper bounds, and the family is flexible enough that, when the objective is a weighted sum of worst-case and average-case cost, it supplies the first Pareto frontier for the single-agent problem. The paper also proves the optimal worst-case cost for inspecting any arc of length $c$, which simultaneously recovers, by partitioning the perimeter equally among agents, the known optimal worst-case results for $n=2,3,4,\dots$ agents.

Load-bearing premise

The systematic approximation guarantee rests on the assumption that the true optimal inspection trajectory never touches the disk; if that fails, the claim that the discrete solution is within $1+1/k$ of the continuous optimum is unproved, though each constructed trajectory still gives a valid upper bound.

Editorial extensions

If this is right

  • For $n\ge 3$ agents, the new average inspection time is $\frac{n}{2\pi}\log\frac{1+\sin(\pi/n)}{1-\sin(\pi/n)}$, which asymptotically behaves as $1+\frac{\pi^2}{6n^2}$, so a large team can inspect the perimeter in essentially the minimum time needed to reach the boundary.
  • The worst-case partial-inspection theorem covers every arc length $c$, so the paper's Corollary 2 subsumes the known optimal worst-case results for $n=2,3,4,\dots$ agents in a single proof.
  • The single-agent Pareto curve gives a family of operating points between the worst-case-optimal trajectory (cost $\approx 6.397$) and the average-case-optimal trajectory (length $\approx 6.867$), so a designer can choose how much worst-case guarantee to sacrifice for better average performance.
  • The paper's correction of Gluss's numerical evaluations means that the previously accepted 'best' average-case bounds from 1961 were too optimistic; the new construction is the first genuine improvement.
  • Under the no-touch assumption, the discretization-plus-NLP methodology yields upper bounds that are within $1+1/k$ of the continuous optimum, so increasing $k$ gives a systematic way to approach the true optimum.

Reading between the lines

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

  • If the no-touch assumption can be proved (as the follow-up work cited by the authors suggests), the same NLP pipeline becomes a certified approximation scheme for the disk problem and might extend to any convex obstacle whose visibility is defined by tangent half-planes.
  • The gap between the paper's best single-agent bound ($3.5509015$) and the subsequently proved optimum ($3.549259$) is about $0.0016$, so a natural test is whether increasing $k$ in the same pipeline closes the gap completely.
  • Because the lift in Lemma 4 is one-way (discrete to continuous), the same discretization technique could be adapted to other search and evacuation problems where worst- and average-case guarantees are both of interest.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper studies n unit-speed agents that start at the center of a unit disk and must inspect every point of the disk perimeter, where a perimeter point is covered only if an agent outside the disk has unobstructed visibility of it. It proves a worst-case optimal bound for the partial inspection problem P(c) (Theorem 1), derives the n-agent worst-case bound as a corollary (Theorem 2), proposes average-case upper bounds for S_n using the Extended-PolySegment (EPS) trajectory family and nonlinear programming (Theorem 3), and gives Pareto upper bounds for the trade-off between worst-case and average-case inspection cost (Theorem 4). The paper also identifies numerical errors in Gluss's 1961 heuristic evaluations and provides corrected values.

Significance. If the results stand, the paper makes three useful contributions: it extends Isbell's worst-case shoreline result to partial arcs and thereby gives a unified proof of known multi-agent worst-case bounds; it improves on Gluss's corrected average-case heuristics, including a clean analytic bound for n≥3 agents; and it introduces a tractable parametric family (EPS) for exploring worst-/average-case trade-offs. The correction of Gluss's numerical errors is careful and valuable. The main caveats are that the headline numerical upper bounds for n=1,2 are computer-assisted without accompanying code or data, and the claimed systematic (1+1/k)-approximation guarantee for the discretization-plus-NLP method is not actually proved. These issues are fixable, but they currently affect the strength of the advertised methodology.

major comments (3)
  1. [Section 2.3.2 and Lemma 4] The claim that the NLP solution is "guaranteed to be within 1+1/k of the true optimum" is not supported by the results proved in the paper. Lemma 4 shows only one direction: any feasible discrete PolySegment trajectory lifts to a feasible continuous trajectory whose average cost is at most (1+1/k) times the discrete cost. This gives an upper bound on the continuous optimum in terms of a particular discrete feasible trajectory, but it does not bound the gap between the discrete NLP optimum and the continuous optimum. The reverse direction, in which a non-touching continuous optimal trajectory is rounded to a PolySegment with vertices on the tangent lines L_i, is never proved, and the stated "no-touch" assumption is not used in any lemma. The individual upper bounds in Theorem 3 remain valid as feasible constructions, but the systematic-convergence claim in Section 2.3.2 should either be proved or explicitly restated as a heuristic with one-sided certificates.
  2. [Section 4.2, Theorem 3, and Theorem 4] The numerical upper bounds for n=1,2 and the Pareto curve are not reproducible from the manuscript. The proof of Theorem 8 reports solutions of (NLP-avg(k,c,epsilon)) obtained with Ipopt for k=1000 and k=2000, but no code, data files, or explicit optimizer vectors (theta,t_1,...,t_k) are provided; the figures showing the t_i values cannot be used to certify the quoted numbers. Since the values 3.5509015 and 1.7946051 are central to the claimed improvement over Gluss's corrected bounds, the authors should provide the feasible trajectories as high-precision data or as runnable code. The same concern applies to Theorem 4, whose statement refers to a figure rather than to an explicit table or data set supporting the Pareto upper bounds.
  3. [Appendix A.1, Lemma 7] The displayed derivative f1'(theta)=(sin(theta)-sin(theta))/cos(theta) is identically zero, so the monotonicity analysis in Lemma 7 is invalid as printed. The correct derivative appears to be (sin(theta)-sin(c))/cos^2(theta); with this correction the case analysis can be repaired, but the proof of Theorem 1 needs to be updated accordingly. In addition, the proof of Theorem 1 invokes Isbell's convexity theorem as a black box; since that theorem is the main geometric input for the partial-arc extension, the authors should state explicitly that it is an external result and explain how it carries over to the partial-arc setting.
minor comments (3)
  1. [Section 6] The Discussion invokes reference [39] as "subsequent work" that validates the approach and gives a true optimum of 3.549259. This reference is an arXiv preprint by one of the authors, so it is not independent confirmation; the provenance and status of the result should be stated clearly.
  2. [Section 2.2 and Theorem 3] The asymptotic statement that the average cost converges to 1 + pi^2/(6 n^2) + o(1/n^3) is asserted without derivation; a short expansion or an explicit reference would make the claim easier to verify.
  3. [Figures 10 and 15] Several figure captions and axis labels appear corrupted in the full text (e.g., strings like "i255/3/7/8/9"), which makes the figures difficult to read. These should be regenerated or relabeled.

Circularity Check

1 steps flagged · score 2.0 of 10

No derivation-level circularity: the upper bounds are feasible constructions with independently computed costs. The only circularity signal is a discussion-level self-citation to the same author's follow-up preprint for optimality, plus an advertised (1+1/k)-optimality guarantee that is not actually proved.

  1. self citation load bearing [Section 6, Discussion]
    "subsequent work has shown that the methodology we develop here, after substantial additional technical work, does yield the true optimum of the average-case Disk-Inspection problem [39]. The optimal cost was proved to be 3.549259, only slightly below our best reported upper bound of 3.5509015. The proof relies crucially on the nonlinear programming framework introduced here."

    The paper validates its own methodology by citing [39], a same-author preprint that, by the paper's own statement, relies crucially on the nonlinear programming framework introduced in the present paper. This creates a self-referential loop: the follow-up proves optimality using the framework, and the present paper cites the follow-up as the authority that the framework yields the true optimum. The circularity is discussion-level only; it is not used to derive Theorem 3, whose costs come from feasible trajectories evaluated directly, so it raises the score mildly rather than invalidating the upper bounds.

full rationale

The core stated results are self-contained upper-bound constructions. The EPS and PS trajectories are defined geometrically and their average and worst-case costs are computed from the trajectory lengths and inspection times (Lemmas 2-5), so the reported average costs in Theorem 3 and the Pareto bounds in Theorem 4 are not fitted to a target value. The worst-case results build on Isbell's external convexity theorem and on known lower bounds from [1,30], not on the authors' own prior results. The NLP objective is not a disguised target: Lemma 5 shows it exactly equals the cost of a feasible EPS trajectory, so optimizing it yields legitimate upper bounds. No equation in the paper reduces an output to its own input by definition. Two caveats do not amount to input-output circularity. First, the Section 2.3.2 claim that the NLP solution is guaranteed to be within 1+1/k of the true optimum is not established: Lemma 4 only shows a one-way lift from discrete PolySegment trajectories to feasible continuous trajectories, and because the NLP optimizes over a restricted trajectory family, the discrete optimum need not be a lower bound on the continuous optimum. This is a rigor gap, not a circular reduction. Second, the Discussion's reliance on [39], a same-author preprint that itself depends on this paper's framework, is a self-citation loop, but it is not load-bearing for the formal upper bounds. The score of 2 reflects that minor self-citation, not a definitional or fitted-input circularity.

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

Central claims rest on standard search-theory definitions, one inherited geometric convexity theorem, and numerical solver outputs. No new physical or mathematical entities are introduced. The main unproved inputs are Isbell's convexity and the no-touch discretization approximation.

free parameters (3)
  • EPS deployment angle theta for S1 = 0.5910554
    NLP-optimized decision variable in EPS(theta,t1,...,tk) with k=2000; the S1 average-case bound 3.5509015 is the objective value for this theta.
  • EPS deployment angle theta for S2 = 0.8054878
    NLP-optimized for c=pi, k=2000; supports the S2 average-case bound 1.7946051.
  • Tangent parameters t_1,...,t_k = k=2000 values shown graphically in Figure 14, not tabulated
    Coordinates of the polysegment trajectory; the reported S1 and S2 numbers depend on these values, which are not enumerated in the text.
assumptions (4)
  • domain assumption Isbell's theorem that an optimal inspection curve is convex about the origin
    Invoked in the proof of Theorem 1 to restrict candidate curves to type-1 and type-2; cited from [48], not proved here. Load-bearing for the worst-case optimality result.
  • ad hoc to paper The globally optimal trajectory for the continuous average-case problem does not touch the disk
    Stated in Section 2.3.2 as the condition for the (1+1/k)-approximation guarantee. Only a one-way lift is proved in Lemma 4; the reverse direction is not established in this paper.
  • domain assumption Ipopt/JuMP outputs are feasible and locally optimal for NLP-avg(k,c,epsilon)
    The numerical upper bounds rely on solver outputs; no code or certificates are shipped, and local optimality does not imply global optimality.
  • domain assumption Average case is uniform over perimeter points, equivalent to randomizing the disk rotation
    This is the definition of average-case used throughout Section 2.1 and underlies all average-case results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Disk and Partial Disk Inspection: Worst- to Average-Case and Pareto Upper Bounds." pith.science (2026). https://pith.science/paper/64MPCOVI

@misc{pith2026241115391,
  author       = {Pith},
  title        = {Pith review of: Disk and Partial Disk Inspection: Worst- to Average-Case and Pareto Upper Bounds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/64MPCOVI}},
  note         = {Machine review of arXiv:2411.15391}
}
abstract

We consider $n$ unit-speed mobile agents initially positioned at the center of a unit disk, tasked with inspecting all points on the disk's perimeter. A perimeter point is considered covered if an agent located outside the disk's interior has unobstructed visibility of it, treating the disk itself as an obstacle. For $n=1$, this problem is known as the shoreline problem with a known distance. Isbell (1957) derived an optimal trajectory that minimizes the worst-case inspection time for this problem, while Gluss (1961) proposed heuristics for its average-case version. The one-agent case was originally introduced as a more tractable variant of Bellman's famous lost-in-the-forest problem. Our contributions are threefold. First, as a warm-up, we extend Isbell's findings by deriving worst-case optimal trajectories for partial inspection of a section of the disk, thereby providing an alternative proof of optimality for inspection with $n \geq 2$ agents. Second, we improve Gluss's bounds on the average-case inspection time under a uniform distribution of perimeter points (equivalent to randomized inspection algorithms), and we also strengthen the methodology by combining spatial discretization with Nonlinear Programming (NLP) to build feasible solutions to the continuous problem and compare them with NLP solutions. Third, we establish Pareto-optimal bounds for the multi-objective problem of jointly minimizing the worst-case and average-case inspection times.

Figures

Figures reproduced from arXiv: 2411.15391 by the authors.

Figure 1
Figure 1. Agent’s trajectories of Theorem 3 for n “ 1, 2. corresponding to solutions for Ppcq with c “ π and c “ 2π [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Our Pareto upper bounds are depicted in orange and are achieved by the Extended [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Previously known trajectories for Disk Inspection [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (13 more)
Figure 4
Figure 4. Figure 4: Supporting figures for Lemma 1. For this, consider an arbitrary point Pt on the disk. The line passing through A,Pt is tangent to the disk if and only if ÝÝÑOPt “ pcosptq,sinptqq is orthogonal to ÝÝÑPtA “ pr cospϕq ´ cosptq, r sinpϕq ´ sinptqq. But then, we see that ÝÝ…
Figure 5
Figure 5. Figure 5: Visualization of the results in Theorem 1, and Theorem 8. A visualization of Theorem 1 is provided in [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Trajectories achieving the worst-case optimal inspection cost to [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: In this example k “ 4, and we demonstrate how PSpt1, . . . , t4q is feasible to Ap4, θ, cq. The disk segment of arc length c ´ 2θ, whose perimeter needs to be inspected, is depicted as the light blue sector. The tangent lines Liptq are depicted as dotted red lines, whe…
Figure 8
Figure 8. Figure 8: The inspection time of points Pϕ, where ϕ P r0, θs, in the initial movement O Ñ A0 of the trajec￾tory ExtendedPolySegment. Next, and for each ϕ P r0, θs we calculate the inspection time IpPϕq of Pϕ, depicted as point P in [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: The reported average inspection cost (in blue) of algorithm [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]
Figure 10
Figure 10. Figure 10: Trajectories for minimizing the average inspection cost for [PITH_FULL_IMAGE:figures/full_fig_p022_10.png]
Figure 11
Figure 11. Figure 11: The last phase of the Isbell-type algorithm for [PITH_FULL_IMAGE:figures/full_fig_p024_11.png]
Figure 12
Figure 12. Figure 12: The value of the initial deployment angle [PITH_FULL_IMAGE:figures/full_fig_p025_12.png]
Figure 13
Figure 13. Figure 13: Agent’s trajectories for trade-off problem [PITH_FULL_IMAGE:figures/full_fig_p026_13.png]
Figure 14
Figure 14. Figure 14: Inspection parameter values of ti for the extended polysegment algorithm, as used in Theorem 3 [PITH_FULL_IMAGE:figures/full_fig_p032_14.png]
Figure 15
Figure 15. Figure 15: Trajectories for minimizing the average inspection cost for [PITH_FULL_IMAGE:figures/full_fig_p033_15.png]
Figure 16
Figure 16. Figure 16: Agent’s trajectories’ parameter values ti for trade-off problem T pλq of the proof of Theorem 3, for λ “ 1, 2{3, 1{3. The parameter values corresponding to λ “ 0 (i.e. the best average performance of EPSpθ, t1, . . . , tkq solving S1) can be seen in Figure 14b. Notabl…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 45 canonical work pages

  1. [39]

    Optimal average disk-inspection via Fermat’s Principle.arXiv preprint arXiv:2509.06334, 2025

    K Georgiou. Optimal average disk-inspection via Fermat’s Principle.arXiv preprint arXiv:2509.06334, 2025

    work page arXiv 2025

  2. [1]

    Acharjee, K

    S. Acharjee, K. Georgiou, S. Kundu, and A. Srinivasan. Lower bounds for shoreline search- ing with 2 or more robots. In23rd OPODIS, volume 153 ofLIPIcs, pages 26:1–26:11. Schloss Dagstuhl - LZI, 2019

    work page 2019

  3. [2]

    Ahlswede and I

    R. Ahlswede and I. Wegener.Search problems. John Wiley & Sons, Inc., 1987

    work page 1987

  4. [3]

    Alpern, R

    S. Alpern, R. Fokkink, L. Gasieniec, R. Lindelauf, and V. S. Subrahmanian.Search theory. Springer, 2013

    work page 2013

  5. [4]

    Alpern and S

    S. Alpern and S. Gal.The theory of search games and rendezvous, volume 55. Springer Science & Business Media, 2006

    work page 2006

  6. [5]

    Angelopoulos, C

    S. Angelopoulos, C. Dürr, and T. Lidbetter. The expanding search ratio of a graph.Discret. Appl. Math, 260:51–65, 2019

    work page 2019

  7. [6]

    Baeza-Yates

    R. Baeza-Yates. Searching: an algorithmic tour.Encyclopedia of Computer Science and Technology, 37:331–359, 1997

    work page 1997

  8. [7]

    Baeza-Yates and R

    R. Baeza-Yates and R. Schott. Parallel searching in the plane.Computational Geometry, 5(3):143–154, 1995

    1995

Show all 61 references
  1. [8]

    R. A. Baeza-Yates, J. C. Culberson, and G. J. E. Rawlins. Searching with uncertainty. In Scandinavian Workshop on Algorithm Theory, pages 176–189. Springer, 1988

    1988

  2. [9]

    Searchingintheplane.Information and computation, 106(2):234–252, 1993

    R.A.Baezayates,J.C.Culberson,andG.J.E.Rawlins. Searchingintheplane.Information and computation, 106(2):234–252, 1993

    1993

  3. [10]

    Bagheri, L

    I. Bagheri, L. Narayanan, and J. Opatrny. Evacuation of equilateral triangles by mobile agents of limited communication range. In F. Dressler and C. Scheideler, editors,ALGO- SENSORS 2019, volume 11931 ofLecture Notes in Computer Science, pages 3–22. Springer, 2019

    2019

  4. [11]

    Bampas, J

    E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, R. Klasing, T. Kociumaka, and D. Pa- jak. Linear search by a pair of distinct-speed robots.Algorithmica, 81(1):317–342, 2019

    2019

  5. [12]

    A. Beck. On the linear search problem.Israel Journal of Mathematics, 2(4):221–228, 1964

    1964

  6. [13]

    Behrouz, O

    P. Behrouz, O. Konstantinidis, N. Leonardos, A. Pagourtzis, I. Papaioannou, and M. Spyrakou. Byzantine fault-tolerant protocols for (n, f)-evacuation from a circle. In International Symposium on Algorithmics of Wireless Networks, pages 87–100. Springer, 2023

    2023

  7. [14]

    R. Bellman. Minimization problem.Bull. Amer. Math. Soc, 62(3):270, 1956

    1956

  8. [15]

    R. Bellman. Dynamic programming.Chapter IX, Princeton University Press, Princeton, New Jersey, 1958

    1958

  9. [16]

    R. Bellman. An optimal search.Siam Review, 5(3):274, 1963

    1963

  10. [17]

    Berzsenyi

    G. Berzsenyi. Lost in a forest (a problem area initiated by the late richard e. bellman). Quantum (November/December, 1995), 41, 1995

    1995

  11. [18]

    Bonato, K

    A. Bonato, K. Georgiou, C. MacRury, and P. Prałat. Algorithms for p-faulty search on a half-line.Algorithmica, pages 1–30, 2022

    2022

  12. [19]

    Bouchard, Y

    S. Bouchard, Y. Dieudonné, A. Pelc, and F. Petit. Deterministic treasure hunt in the plane with angular hints. In29th International Symposium on Algorithms and Computation, ISAAC 2018, volume 123, pages 48–1. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018

    2018

  13. [20]

    Brandt, K.-T

    S. Brandt, K.-T. Foerster, B. Richner, and R. Wattenhofer. Wireless evacuation on m rays with k searchers.Theor. Comput. Sci, 811:56–69, 2020

    2020

  14. [21]

    Chrobak, L

    M. Chrobak, L. Gasieniec, T. Gorry, and R. Martin. Group search on the line. In G. F. Italiano, T. Margaria-Steffen, J. Pokorný, J.-J. Quisquater, and R. Wattenhofer, editors, 28 J. Conley and K. Georgiou SOFSEM, volume 8939 ofLecture Notes in Computer Science, pages 164–176. ...

    2015

  15. [22]

    Chuangpishit, K

    H. Chuangpishit, K. Georgiou, and P. Sharma. A multi-objective optimization problem on evacuating 2 robots from the disk in the face-to-face model; trade-offs between worst-case and average-case analysis.Information, 11(11):506, 2020

    2020

  16. [23]

    Ipopt: Interior point optimizer.https://github.com/coin-or/Ipopt

    COIN-OR. Ipopt: Interior point optimizer.https://github.com/coin-or/Ipopt. Ac- cessed: 2024-06-19

    2024

  17. [24]

    Conley and K

    J. Conley and K. Georgiou. Multi-agent disk inspection. In Ulrich Schmid and Roman Kuznets, editors,Structural Information and Communication Complexity (SIROCCO’25), pages 262–280, Cham, 2025. Springer Nature Switzerland

    2025

  18. [25]

    Czyzowicz, L

    J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak. Evacuating robots via unknown exit in a disk. In F. Kuhn, editor,DISC 2014, volume 8784 ofLecture Notes in Computer Science, pages 122–136. Springer, 2014

    2014

  19. [26]

    Czyzowicz, K

    J. Czyzowicz, K. Georgiou, M. Godon, E. Kranakis, D. Krizanc, W. Rytter, and M. Wlo- darczyk. Evacuation from a disc in the presence of a faulty robot. In S. Das and S. Tixeuil, editors,SIROCCO 2017, volume 10641 ofLecture Notes in Computer Science, pages 158–

    2017

  20. [27]

    Czyzowicz, K

    J. Czyzowicz, K. Georgiou, and E. Kranakis. Group search and evacuation. In P. Flocchini, G. Prencipe, and N. Santoro, editors,Distributed Computing by Mobile Entities; Current Research in Moving and Computing, chapter 14, pages 335–370. Springer, 2019

    2019

  21. [28]

    Czyzowicz, E

    J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. M. Shende. Wireless autonomous robot evacuation from equilateral triangles and squares. In S. Pa- pavassiliou and S. Ruehrup, editors,14th International Conference, ADHOC-NOW, volume 9143 ofLecture Notes i...

    2015

  22. [29]

    Czyzowicz, E

    J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. M. Shende. Linear search with terrain-dependent speeds. In D. Fotakis, A. Pagourtzis, and V. Th. Paschos, editors,Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 2...

    2017

  23. [30]

    Dobrev, R

    S. Dobrev, R. Královič, and D. Pardubská. Improved lower bounds for shoreline search. InInternational Colloquium on Structural Information and Communication Complexity, pages 80–90. Springer, 2020

    2020

  24. [31]

    Dunning, J

    I. Dunning, J. Huchette, and M. Lubin. Jump: A modeling language for mathematical optimization.SIAM review, 59(2):295–320, 2017

    2017

  25. [32]

    Y. Emek, T. Langner, D. Stolz, J. Uitto, and R. Wattenhofer. How many ants does it take to find the food?Theoretical Computer Science, 608:255–267, 2015

    2015

  26. [33]

    Y. Emek, T. Langner, J. Uitto, and R. Wattenhofer. Solving the ants problem with asyn- chronous finite state machines. InProceedings of International Colloquium on Automata, Languages, and Programming (ICALP), LNCS 8573, pages 471–482, 2014

    2014

  27. [34]

    S. P. Fekete, C. Gray, and A. Kröller. Evacuation of rectilinear polygons. In W. Wu and O. Daescu, editors,Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I, volume 6508 ofLec...

    2010

  28. [35]

    S. R. Finch and J. E. Wetzel. Lost in a forest.The American Mathematical Monthly, 111(8):645–654, 2004

    2004

  29. [36]

    S. R. Finch and L.-Y. Zhu. Searching for a shoreline.arXiv preprint math/0501123, 2005

    2005 arXiv

  30. [37]

    G. M. Fricke, J. P. Hecker, A. D. Griego, L. T. Tran, and M. E. Moses. A distributed deter- ministic spiral search algorithm for swarms. In2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4430–4436. IEEE, 2016. Disk and Partial Disk Inspec...

    2016

  31. [38]

    Searchgames.Wiley Encyclopedia of Operations Research and Management Science, 2010

    S.Gal. Searchgames.Wiley Encyclopedia of Operations Research and Management Science, 2010

    2010

  32. [40]

    Georgiou and W

    K. Georgiou and W. Jang. Triangle evacuation of 2 agents in the wireless model. InAlgo- rithmics of Wireless Networks: 18th International Symposium on Algorithmics of Wireless Networks, ALGOSENSORS 2022, Potsdam, Germany, September 8–9, 2022, Proceedings, pages 77–90. Springer, 2022

    2022

  33. [41]

    Georgiou, C

    K. Georgiou, C. Jones, and J. Lucier. Multi-agent search-type problems on polygons. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 314–332. Springer, 2025

    2025

  34. [42]

    Georgiou, C

    K. Georgiou, C. Jones, and M. Madej. Spirals and beyond: Competitive plane search with multi-speed agents.arXiv preprint arXiv:2508.10793, 2025

    2025

  35. [43]

    Georgiou, S

    K. Georgiou, S. Leizerovich, J. Lucier, and S. Kundu. Evacuating fromℓp unit disks in the wireless model.Theoretical Computer Science, 944:113675, 2023

    2023

  36. [44]

    Georgiou and J

    K. Georgiou and J. Lucier. Weighted group search on a line & implications to the priority evacuation problem.Theoretical Computer Science, 939:1–17, 2023

    2023

  37. [45]

    P. Gibbs. Bellman’s escape problem for convex polygons, 2016

    2016

  38. [46]

    lost at sea

    B. Gluss. An alternative solution to the “lost at sea” problem.Naval Research Logistics Quarterly, 8(1):117–122, 1961

    1961

  39. [47]

    B. Gluss. The minimax path in a search for a circle in a plane.Naval Research Logistics Quarterly, 8(4):357–360, 1961

    1961

  40. [48]

    J. R. Isbell. An optimal search pattern.Naval Research Logistics Quarterly, 4(4):357–359, 1957

    1957

  41. [49]

    Jeż and J

    A. Jeż and J. Łopuszański. On the two-dimensional cow search problem.Information Processing Letters, 109(11):543–547, 2009

    2009

  42. [50]

    J. M. Kleinberg. On-line search in a simple polygon. InSODA, volume 94, pages 8–15. Citeseer, 1994

    1994

  43. [51]

    Kübel and E

    D. Kübel and E. Langetepe. On the approximation of shortest escape paths.Computational Geometry, 93:101709, 2021

    2021

  44. [52]

    Langetepe

    E. Langetepe. On the optimality of spiral search. InProceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1–12. SIAM, 2010

    2010

  45. [53]

    Langetepe

    E. Langetepe. Searching for an axis-parallel shoreline.Theoretical Computer Science, 447:85–99, 2012

    2012

  46. [54]

    Langner, B

    T. Langner, B. Keller, J. Uitto, and R. Wattenhofer. Overcoming obstacles with ants. In E. Anceaume, C. Cachin, and M. G. Potop-Butucaru, editors,International Conference on Principles of Distributed Systems (OPODIS), volume 46 ofLIPIcs, pages 9:1–9:17. Schloss Dagstuhl - Leib...

    2015

  47. [55]

    Pattanayak, H

    D. Pattanayak, H. Ramesh, P. S. Mandal, and S. Schmid. Evacuating two robots from two unknown exits on the perimeter of a disk with wireless communication. InProceedings of the 19th International Conference on Distributed Computing and Networking, pages 1–4, 2018

    2018

  48. [56]

    A. Pelc. Reaching a target in the plane with no information.Information Processing Letters, 140:13–17, 2018

    2018

  49. [57]

    Pelc and R

    A. Pelc and R. N. Yadav. Information complexity of treasure hunt in geometric terrains. arXiv preprint arXiv:1811.06823, 2018

    2018 arXiv

  50. [58]

    Pelc and R

    A. Pelc and R. N. Yadav. Cost vs. information tradeoffs for treasure hunt in the plane. arXiv preprint arXiv:1902.06090, 2019

    1902 arXiv

  51. [59]

    D. O. Shklarsky, N. N. Chentzov, and I. M. Yaglom.The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics, Part 2, Volume II. Nauka Publishers, Moscow, 1962. 30 J. Conley and K. Georgiou A Omitted Proofs A.1 Proofs Omitted from Section 3.2 Lemm...

    1962

  52. [60]

    min cPrπ{2,2π{3s tf1pθ1q,f 2pθ2qu“min

    For this we rely on the derivative f1 1pθq“psinpθq´sinpθqq{cospθq. Next we examine cases for the range of parameterc. Case 1: If0ďcďπ{2, we have that thatf 1 1pθq“0if and only ifθ“c(for0ďθăπ{2), whereasf 1 1p0q“´sinpcqă0. This means that the function is initially decreasing, u...

  53. [61]

    First it is easy to see that g1 1pcq“ 1 16 sec2 ´c 2 ¯ sec2 ˆ 1 8p2c`πq ˙´ ´4 sin ´c 2 ¯ ´2 sin ´ c` π 4 ¯ `2 cospcq` ? 2`2 ¯

    Hence, it suffices to show thatg1pcqis decreasing. First it is easy to see that g1 1pcq“ 1 16 sec2 ´c 2 ¯ sec2 ˆ 1 8p2c`πq ˙´ ´4 sin ´c 2 ¯ ´2 sin ´ c` π 4 ¯ `2 cospcq` ? 2`2 ¯ . Hence, it suffices to show thath1pcq “ ´4 sin `c 2 ˘ ´2 sin ` c` π 4 ˘ `2 cospcq` ? 2`2ă0for cP rπ...

    2000

Pith tools

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