{"id":"709e0a85-e83f-43d5-9120-948b01923f12","arxiv_id":"2501.00120","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Dynamic unit-disk range reporting queries now run in O(log n + k) time, matching the static bound with the same update costs as before.","lead":"This paper presents a data structure that reports all points inside any fixed-radius circle in near-optimal time, even when points are added and removed. It introduces a fast way to precompute coarse summaries of circular curves, a tool that may carry over to other geometric problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 8 is asserted by a one-paragraph analogy to the line/plane shallow-cutting hierarchy; the dynamic O(log n + k) query bound rests on it, and the arc case is not actually proved.","rationale":"I read the paper as a theory contribution whose headline is the first optimal O(log n + k) dynamic query time for unit-disk range reporting. The static construction and the static arc shallow-cutting algorithm are worked out in detail, and I do not see an obvious contradiction or false lemma in those parts. The dynamic theorem, however, depends on Lemma 8, and Lemma 8 is not proved in the paper; it is imported by analogy. The reader's weakest-assumption analysis identifies exactly this step, and my independent reading confirms it. The concern is not that the claimed result is certainly wrong; it is that the manuscript does not yet supply the argument that the line/plane hierarchy survives the replacement of lines by arcs. In particular, the coverage property 3 and the amortized maintenance of the hierarchy are both subtle enough that a one-sentence transfer is not a proof. I therefore agree with the CONDITIONAL verdict: the paper should be accepted only if this gap is closed, either by a full proof of Lemma 8 for arcs or by a verified derivation following the cited sources step by step. No change to the reader's verdict is needed; the appropriate action is to require the missing proof before treating Theorem 1 as established.","tokens_in":42028,"tokens_out":24634,"duration_ms":248041,"concrete_test":"Independently re-derive Lemma 8 for arcs by expanding the proof of [11, Theorem 3.1] with [12]'s amortization, replacing line/plane shallow cuttings by Theorem 2 at every occurrence, and explicitly verifying properties 1-4 for bottom-open pseudo-trapezoid cells over bounded x-monotone arcs. In particular, check property 3 at a vertical line where fewer than i_k arcs exist, and verify that the interval-tree update argument in [11] remains valid when a cell's x-projection, rather than a line's full extent, is the interval stored. Stop at the first claim that is false for arcs; if none exists, the conditional concern is resolved. As a secondary empirical check on small instances (n up to 2^12), simulate the hierarchy of Lemma 8 with random arcs and compare k-lowest-arcs queries against brute force to detect any concrete counterexample to property 3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim Theorem 1 is reduced to Lemma 4, and Lemma 4 is in turn reduced to Lemma 8 in Section 5.2.2. Lemma 8 supplies the four properties that make the dynamic k-lowest-arcs data structure correct: per-level cutting sizes, deletion-only conflict lists of size O(n/2^i), the coverage guarantee that every candidate arc appears in some list queried at level i_k, and the total-size invariant. The proof of Lemma 8 is a single paragraph: it says the result follows [11, Theorem 3.1] with [12]'s improvement, and that 'we replace their shallow cutting algorithm by ours in Theorem 2 for Γ. Everything else is the same.' This is the point where the paper's new arc machinery is coupled to a nontrivial dynamic hierarchy that was designed for lines and planes. In particular, property 3 is what lets the query inspect only O(log_b n) cells at level i_k and still be certain that the k lowest arcs are all present in the inspected lists. If any step in Chan's proof uses a line-specific fact, for example that every line intersects every vertical line, or that cells are unbounded trapezoids bounded by global lines, the arc setting requires a separate argument because arcs are bounded, x-monotone, and may be absent from some vertical lines. The paper does not provide that argument. Since Theorem 1 inherits its query time from Lemma 4 through Lemma 8, an unverified transfer at this exact point is the most load-bearing weakness in the paper. Other components, such as the conforming coverage maintenance and the static construction, receive substantially more detailed proofs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies dynamic unit-disk range reporting: maintain a set P of n points under insertions and deletions so that all points inside a query unit disk can be reported. The main claimed result (Theorem 1) is an O(n log n)-space structure with O(log^{3+eps} n) amortized insertion, O(log^{5+eps} n) amortized deletion, and optimal O(log n + k) query time, improving the previous query bound of O(log^2 n / log log n + k). The method reduces the problem to dynamic line-separable unit-disk reporting, then to dynamic k-lowest-arcs queries over a set of x-monotone unit-circular arcs. The main new technical ingredient is a shallow cutting algorithm for such arcs (Theorem 2, proved in Section 6 with a detailed charging argument). The dynamic k-lowest-arcs structure (Lemma 4) is obtained by adapting the shallow-cutting hierarchy of Chan and de Berg--Staals for lines/planes; the key transfer is Lemma 8, whose proof is a one-paragraph assertion that the line-based hierarchy carries over once the line cutting routine is replaced by the authors' arc cutting routine. The paper also gives a simpler static O(log n + k) unit-disk reporting structure and improved dynamic unit-disk emptiness queries.","tokens_in":42378,"tokens_out":15371,"duration_ms":156659,"significance":"If the main dynamic claim is correct, it is a significant result: it is the first dynamic unit-disk range reporting structure with optimal O(log n + k) query time while preserving the previous update bounds. The static construction, though matching the known optimal bounds of Afshani--Chan, is genuinely simpler and uses elementary tools. The shallow cutting algorithm for circular arcs is developed in detail, with a careful size proof, and is likely to be useful independently. The dynamic emptiness byproduct is also an improvement over the previous nearest-neighbor-based bounds. The paper is not circular: epsilon, b, and r are asymptotic balancing parameters rather than fitted constants. However, the central dynamic theorem rests on Lemma 8, and that lemma is not proved in the manuscript; this is the main weakness.","major_comments":[{"comment":"Lemma 8 is the load-bearing transfer from the line/plane dynamic shallow-cutting hierarchy to the arc setting, and its proof is a single paragraph: it states that Lemma 8 follows from [11, Theorem 3.1] with the improvement of [12], and that 'we replace their shallow cutting algorithm by ours in Theorem 2 for Γ. Everything else is the same.' This is not a proof of the four stated properties. The line-based hierarchy uses cuttings that cover the whole plane and whose cells are unbounded trapezoids meeting every vertical line; the arc cuttings of Theorem 2 are shallow cuttings covering only the (<=k)-level, with bottom-open pseudo-trapezoid cells, and the statement later in the query description that 'the x-projections of T_i^j partition the x-axis into intervals' is not justified for such shallow cuttings. The proof also does not explain how the rebuilding schedule, the interval trees over x-projections, the deletion-only conflict lists, or property (3) -- the guarantee that every candidate arc appears in some list queried at level i_k -- survive the replacement. Since Theorem 4, Lemma 4, and hence Theorem 1 inherit their query and update bounds from Lemma 8, this missing argument is a genuine gap, not a presentation issue. The authors should supply a complete proof of Lemma 8, or state and prove an explicit arc-specific version of the dynamic hierarchy.","section":"Section 5.2.2, Lemma 8"},{"comment":"Lemma 7 is likewise asserted by analogy: it is said to be 'obtained by following the same algorithmic scheme as [7, Lemma 6] and replacing their shallow cutting algorithm for lines with our shallow cutting algorithm for arcs of Γ in Theorem 2.' This lemma is used in the second case of the proof of Lemma 4, for conflict lists of size m < log^3 n, and it is needed to obtain the final O(log n + k) query bound. The same concerns as for Lemma 8 apply: the deletion-only structure in [7, Lemma 6] relies on specific properties of cuttings of planes, and the manuscript does not verify that those properties transfer to bottom-open pseudo-trapezoid shallow cuttings for bounded x-monotone arcs. Lemma 7 should either be proved or replaced by an argument that does not depend on an unverified transfer.","section":"Section 5.2.1, Lemma 7"}],"minor_comments":[{"comment":"There is a typographical error in 'F orming a grid G'; it should read 'Forming a grid G'.","section":"Section 3, first paragraph"},{"comment":"The proof of Lemma 14 states the inequality x(b_i) <= x(b_{i+1}) twice; the second occurrence should presumably be x(a_i) <= x(a_{i+1}), since the goal is to compare the centers via both endpoint orders.","section":"Section 7.1, Lemma 14 proof"},{"comment":"In the second case of the query-time analysis, the text says 'Since m < log^3 m'; this should be 'm < log^3 n'.","section":"Section 5.2.2, case 2"},{"comment":"In the removal step, the line 'As discussed in the proof of Lemma 10, Δ ⊆ H_ℓ({q1,q2})' appears to refer to the cell σ of the epsilon cutting, not the cell Δ of VD(Q_IN,S_IN); the notation should be corrected for readability.","section":"Section 6.3, Step (3) of Theorem 3 proof"},{"comment":"The heading 'F ully-dynamic data structure for Lemma 4' contains a spurious space; it should read 'Fully dynamic data structure for Lemma 4'.","section":"Section 5.2.2, heading"}],"recommendation":"major_revision","confidential_remarks":"The paper has a strong and carefully argued static core: Theorem 3, the arc shallow cutting algorithm, is proved in detail, and the static reporting/emptiness arguments are mostly elementary and self-contained. The main dynamic claim, however, depends on Lemma 8 (and to a lesser extent Lemma 7), and those lemmas are currently asserted by analogy to prior work on lines and planes rather than proved. I do not see an internal contradiction or a circular definition of the target bounds, but the missing transfer is load-bearing. If the authors can supply a rigorous proof of Lemma 8 and Lemma 7 in the arc setting, I would support acceptance; in the present form the central query-time claim is not fully established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real result. The dynamic unit-disk range reporting query time drops to O(log n + k), matching the static bound for the first time, and the main new ingredient—a shallow cutting algorithm for circular arcs—is worked out in enough detail to be believable and reusable on its own. The static structure is a genuinely simpler route to known bounds, not a new complexity, but the simplification is still worth something. The emptiness improvement is a useful byproduct, though it leans more heavily on prior infrastructure.\n\nThe stress test points at the right place. Lemma 8, which supplies the fully dynamic hierarchy of shallow cuttings for arc sets, is transferred from Chan's line/plane construction by a one-sentence analogy: replace the line cutting algorithm with Theorem 2 and keep everything else. That is not a proof for arcs. Arcs are x-monotone and pairwise cross at most once, so much of the machinery plausibly carries over, but line-specific facts like every line intersecting every vertical line fail for bounded arcs. The four properties in Lemma 8 are load-bearing: they guarantee that querying O(log_b n) cells at level i_k finds all k lowest arcs. Without a real argument for the arc case, Theorem 1's query bound is conditional. This is a gap in the presentation, not evidence the claim is false.\n\nThe strongest part of the paper is Theorem 3, the shallow cutting computation itself. The charging argument, the size bound, and the transformations between pseudo-trapezoid and vertex-segment forms are all spelled out in serious detail. I do not see circular reasoning or fitted constants; epsilon, b, and r are ordinary asymptotic balancing parameters.\n\nOther soft spots are minor. Lemmas 5 and 12 lean on Wang's arc partition tree [36], and Section 8 depends on Wang-Zhao [38]; the emptiness section invokes Chan's framework plus the authors' earlier deletion-only structure with fewer details. That is normal within-subfield reliance, not a red flag.\n\nWho is this for: people working on fixed-radius neighbor problems, dynamic range searching, or shallow cuttings for curved objects. The paper deserves a serious referee. The referee's main job is to push on Lemma 8—either a full proof for arcs or an explicit accounting of which line-specific steps change. That is a major-revision-sized request, not a desk reject.","headline":"Genuine query-time improvement plus a reusable arc shallow cutting; one unproved transfer lemma is the load-bearing risk.","tokens_in":673,"tokens_out":743,"would_cite":true,"duration_ms":28201,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","68P05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A dynamic unit-disk range reporting data structure answers each query in $O(\\log n + k)$ time, matching the static optimum while keeping previous space and update bounds.","keywords":["unit-disk range reporting","dynamic data structures","shallow cuttings","circular arcs","range emptiness","alpha-hulls","fractional cascading","conforming coverage"],"falsifier":"Run the paper's arc shallow-cutting algorithm on an adversarial set of unit arcs, for example many arcs with nearly coincident endpoints on the $x$-axis, and verify the claimed per-cell bound: if any bottom-open pseudo-trapezoid cell from the vertex-segment decomposition intersects more than $3K$ arcs, then Observation 4, hence Lemma 11 and Theorem 2, fails. A second check is whether a $k$-lowest-arcs query using the lemma's interval trees ever misses an arc that should be among the $k$ lowest at the query vertical line.","tokens_in":41784,"feed_emoji":"📐","tokens_out":10557,"duration_ms":96610,"temperature":0.7,"pith_summary":"The paper claims that dynamic unit-disk range reporting—maintaining a moving set of points so that a query disk of fixed radius can list all points inside it—can be answered in $O(\\log n + k)$ time, where $k$ is the number of reported points. The previous best dynamic structure took $O(\\log^2 n / \\log\\log n + k)$ per query; the new query time matches the best known static structures and is therefore optimal up to constant factors. The improvement does not change the space or update costs: $O(n\\log n)$ space, $O(\\log^{3+\\epsilon} n)$ amortized insertion, and $O(\\log^{5+\\epsilon} n)$ amortized deletion. The engine is a new shallow-cutting algorithm for equal-radius circular arcs, which the authors also use to give a simpler static structure and to speed up dynamic unit-disk emptiness queries to $O(\\log n)$ per query with $O(\\log^{1+\\epsilon} n)$ updates. If correct, the result closes the gap between dynamic and static query performance for the fixed-radius neighbor problem.","feed_headline":"Unit-disk queries now run in optimal O(log n + k) time","feed_subtitle":"A shallow cutting for circular arcs removes the log-factor gap between dynamic and static unit-disk range reporting.","key_machinery":"The load-bearing object is a shallow cutting for circular arcs: a family of bottom-open pseudo-trapezoid cells, each bounded by two vertical rays, a top edge that is an equal-radius arc or an axis segment, and no bottom boundary, such that every cell intersects at most $K$ arcs and the cells cover the region of depth at most $k$. The paper computes such cuttings in $O(n\\log(n/k))$ time by first building a vertex-segment form $(Q,S)$, where $Q$ is a set of sample points below the $x$-axis and $S$ is a set of disjoint segments on the axis whose vertical decomposition covers the shallow region. The bridge between forms is the line-separated $\\alpha$-hull, defined as the complement of all unit disks with centers above the axis that contain none of $Q$; its vertical decomposition yields the pseudo-trapezoid cells. This arc cutting is then substituted into the known dynamic hierarchy for line reporting, whose interval trees over $x$-projections and deletion-only conflict lists answer $k$-lowest-arcs queries in $O(k + \\log n)$ time.","core_discovery":"The central claim is that the line-based machinery for dynamic halfspace range reporting can be re-derived for equal-radius circular arcs: replace the shallow cutting of lines with a new shallow cutting of unit arcs, and the whole hierarchy carries over. The paper proves the arc cutting exists with an $O(n\\log(n/k))$-time construction, first in a vertex-segment form built from line-separated $\\alpha$-hulls, then converted into bottom-open pseudo-trapezoid form. Lemma 8 asserts that the fully dynamic collection of shallow cuttings inherits the earlier line-based guarantees, which yields $k$-lowest-arcs queries in $O(k + \\log n)$; Observation 2 converts those into arc-below-point reporting, and the conforming coverage grid (Lemma 2) reduces each unit-disk query to $O(1)$ line-separable instances. The claimed consequence is Theorem 1: $O(n\\log n)$ space, $O(\\log^{3+\\epsilon} n)$ insertions, $O(\\log^{5+\\epsilon} n)$ deletions, and $O(\\log n + k)$ queries. A byproduct is a static structure with the same query bound built from elementary techniques, and a dynamic emptiness structure with $O(n)$ space, $O(\\log^{1+\\epsilon} n)$ updates, and $O(\\log n)$ queries.","pith_inferences":["If the line-to-arc transfer in Lemma 8 is sound, the same strategy should apply to other dynamic queries over equal-radius arcs, such as fixed-radius nearest-neighbor or disk-containment problems, yielding query times closer to their static bounds.","The dynamic conforming coverage grid (Lemma 2) is a standalone primitive: any unit-disk problem that needs to touch only $O(1)$ cells per query could reuse it, independent of the arc shallow cutting.","A natural stress test is to instantiate Theorem 2 on adversarial arc arrangements, such as many arcs crossing near a common vertical line, and measure whether cell conflict lists stay within the proved $3K$ bound; unexpected violations would point to where the single-sentence inheritance argument needs care.","The static structure's use of fractional cascading hints that a pointer-machine variant with the same $O(\\log n + k)$ query bound may exist, since fractional cascading is usually a RAM-oriented device; whether the bound survives on a pointer machine is not addressed by the paper."],"forward_implications":["Unit-disk range reporting queries now take optimal $O(\\log n + k)$ time in a dynamic setting, matching the static data structure and removing the previous log-factor gap.","Dynamic unit-disk range emptiness drops to $O(\\log n)$ query time with $O(\\log^{1+\\epsilon} n)$ amortized updates in $O(n)$ space, improving over the previous $O(\\log^2 n)$ query and $O(\\log^4 n)$ deletion costs.","The static UDRR structure achieves $O(n)$ space, $O(n\\log n)$ preprocessing, and $O(\\log n + k)$ queries using elementary techniques, offering a simpler alternative to the 3D halfspace-lifting route.","The arc shallow-cutting algorithm is a reusable primitive: any problem that reduces to reporting arcs below a point, or to $k$-lowest-arcs queries among equal-radius arcs, can adopt the same cutting and inherit its bounds.","Insertions remain at $O(\\log^{3+\\epsilon} n)$ and deletions at $O(\\log^{5+\\epsilon} n)$ amortized time, so the query speedup does not trade off update performance."],"supporting_citations":[{"why":"Establishes the static optimal halfspace range reporting bound that the new $O(\\log n + k)$ query time matches.","marker":"[1]"},{"why":"Provides the previous best dynamic halfspace reporting scheme and the multi-structure querying technique the paper adapts to arcs.","marker":"[7]"},{"why":"Supplies the original dynamic 3-D convex hull framework from which the fully dynamic shallow-cutting hierarchy is derived.","marker":"[10]"},{"why":"Gives the dynamic convex-hull hierarchy (its Theorem 3.1) that Lemma 8 claims to inherit for arcs.","marker":"[11]"},{"why":"Provides the improved shallow-cutting strategy and dynamic data structure bounds used to tune the hierarchy's update time.","marker":"[12]"},{"why":"Gives the line/plane shallow-cutting algorithm whose arc counterpart is the paper's Theorem 2.","marker":"[14]"},{"why":"Contributes the observation that improves the hierarchy and supports the claimed update bounds.","marker":"[28]"},{"why":"Supplies the partition-tree halfplane reporting structure with deletions used in the deletion-only data structures (Lemmas 5 and 6).","marker":"[30]"},{"why":"Provides the conforming coverage construction and the arc partition-tree generalization reused throughout the paper.","marker":"[36]"},{"why":"Establishes the lower-envelope and duality facts for unit arcs used in the static layers and emptiness queries.","marker":"[38]"}],"fun_headline_variants":["Dynamic disk queries now run in O(log n + k)","Shallow arc cutting unlocks faster disk queries","Log-factor gap closed for dynamic disk reporting","Unit-disk updates stay fast, queries hit O(log n + k)","Arc shallow cutting removes reporting bottleneck"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole result rests on the assumption that a standard dynamic construction for finding the lowest lines at a vertical line carries over unchanged to equal-radius circular arcs once the line-cutting subroutine is replaced by an arc-cutting subroutine; the paper asserts this inheritance in a single sentence, so if arcs misbehave at any step, the claimed query bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic disk queries now run in O(log n + k)","Shallow arc cutting unlocks faster disk queries","Log-factor gap closed for dynamic disk reporting","Unit-disk updates stay fast, queries hit O(log n + k)","Arc shallow cutting removes reporting bottleneck"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001712,"raw_usage":{"total_tokens":6878,"prompt_tokens":1148,"completion_tokens":5730,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":764,"completion_tokens_details":{"reasoning_tokens":5657}},"tokens_in":764,"tokens_out":5730,"duration_ms":37477,"temperature":1.0,"reasoning_tokens":5657,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:00:54.586736+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's arc shallow-cutting algorithm on an adversarial set of unit arcs, for example many arcs with nearly coincident endpoints on the $x$-axis, and verify the claimed per-cell bound: if any bottom-open pseudo-trapezoid cell from the vertex-segment decomposition intersects more than $3K$ arcs, then Observation 4, hence Lemma 11 and Theorem 2, fails. A second check is whether a $k$-lowest-arcs query using the lemma's interval trees ever misses an arc that should be among the $k$ lowest at the query vertical line.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the static optimal halfspace range reporting bound that the new $O(\\log n + k)$ query time matches."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the dynamic convex-hull hierarchy (its Theorem 3.1) that Lemma 8 claims to inherit for arcs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the improved shallow-cutting strategy and dynamic data structure bounds used to tune the hierarchy's update time."},{"cited_title":"Chan and Konstantinos Tsakalidis","cited_arxiv_id":null,"evidence_quote":"Gives the line/plane shallow-cutting algorithm whose arc counterpart is the paper's Theorem 2."},{"cited_title":"Computing the minimum bottleneck moving spanning tree","cited_arxiv_id":null,"evidence_quote":"Establishes the lower-envelope and duality facts for unit arcs used in the static layers and emptiness queries."}],"review_version":1}