{"id":"26d9d0cd-408c-4cd8-8084-61a0b7ee464e","arxiv_id":"2412.17138","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Minimum radius balls in metric spaces with the Heine-Borel property, including Hilbert, Thompson, and Funk geometries, are LP-type problems.","lead":"This paper proves that in any metric space where closed bounded sets are compact, the smallest enclosing ball problem has the 'LP-type' structure that makes fast randomized algorithms possible. The authors apply this to the Hilbert and Thompson metrics and the Funk weak metric, and sketch a fast algorithm for minimum enclosing balls in Hilbert polygons.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 14's weak-metric extension is unproven: the boundedness of C_n in Proposition 13 uses symmetry, so the Heine-Borel argument does not apply to forward balls in weak metrics.","rationale":"Proposition 13 and Theorem 16 for symmetric metric spaces are correct: the nested compact intersection argument works, and the LP-type monotonicity and locality proofs are valid. The weak-metric extension, however, is not a corollary of the same proof. The paper states that the proof 'did not use the symmetric property,' but symmetry is used in the boundedness of C_n. Without a forward ball containing each C_n, the Heine-Borel property does not apply, so Corollary 14 is unproven. This is more load-bearing than the Thompson topology citation gap, because Corollary 14 is the sole route to the Funk weak-metric result in Corollary 19; a missing citation in Theorem 9 is easily repaired, while this is a logical gap in a claimed general theorem. The specific Funk application may still be true, as reverse Funk balls are likely forward-bounded, but this must be verified. I recommend keeping the conditional verdict because the core metric-space theorem stands; the paper must supply a corrected proof or restriction of the weak-metric claim.","tokens_in":8412,"tokens_out":25256,"duration_ms":230476,"concrete_test":"Check the boundedness step without symmetry: in the weak metric d(x,y)=max(0,y-x) on R, forward balls are B(c,R)=[c,c+R], and for H={1} the set C_n is [1-(r+1/n), ∞), which is not contained in any forward ball; this space also fails the Heine-Borel property because [0,1] is closed and bounded but not compact. Then identify the missing hypothesis (e.g., reverse balls are forward-bounded) and verify it for the Funk weak metric on a convex polygon by computing a reverse Funk ball B^-(h,M) and checking whether it lies inside a forward Funk ball B(c,R). If reverse Funk balls are forward-bounded, the Funk application in Corollary 19 is sound despite the general proof gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Proposition 13 defines C_n = {p : H ⊆ B(p, r+1/n)} and asserts that each C_n is bounded because d(p,h) ≤ r+1/n for every p ∈ C_n and h ∈ H. In a symmetric metric this implies C_n ⊆ B(h, r+1/n), but according to Definition 2 balls are forward: B(p,r) = {q : d(p,q) ≤ r}. The inequality d(p,h) ≤ r+1/n only places p in the reverse ball {p : d(p,h) ≤ r+1/n}, which need not be contained in any forward ball. Boundedness is therefore not established, and the Heine-Borel hypothesis cannot be applied to C_n. Corollary 14 asserts the minimum ball property for every weak metric with the Heine-Borel property and explicitly claims the proof 'did not use the symmetric property'; this is incorrect, because symmetry is used exactly in the boundedness step. Since Corollary 14 is the basis for the Funk weak-metric case in Corollary 19, a central advertised contribution is unsupported as written. The statement may be salvageable if reverse balls are forward-bounded in the intended applications, but the general theorem requires an added hypothesis or a different argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to prove that the minimum-enclosing-ball problem is LP-type for every metric space satisfying the Heine-Borel property, and extends this claim to weak metric spaces when the direction of balls is fixed. It then applies these results to the Hilbert and Thompson metrics and the Funk weak metric, and sketches an O(n log^3 m) algorithm for Hilbert minimum-enclosing balls of n points in a convex m-gon. The central mechanism is Proposition 13 (Heine-Borel implies existence of minimum radius balls), Theorem 16 (minimum ball property implies LP-type), and Corollary 14/17 extending these to weak metrics. The paper also claims to prove that the Thompson metric induces the Euclidean topology on bounded convex domains.","tokens_in":8591,"tokens_out":5524,"duration_ms":50130,"significance":"If correct, the paper provides a broad sufficient condition for LP-type behavior, covering several non-Euclidean geometries at once and giving a unified explanation for the Euclidean, Hilbert, and Thompson cases. The algorithmic application to Hilbert minimum balls, with a claimed near-linear time bound in the number of input points, would also be of interest to computational geometry. However, the two most novel advertised contributions — the weak-metric extension and the Thompson topology proof — are not supported as written, and the algorithmic primitives rely on unspecified external routines. The core symmetric-metric result (Propositions 13 and Theorem 16) is sound and is a useful observation, but the paper's breadth currently exceeds what its arguments establish.","major_comments":[{"comment":"The proof of Corollary 14 is invalid because the boundedness step in Proposition 13 uses symmetry in an essential way. The proof says 'Each Cn is bounded since for any h∈H and any p∈Cn, d(p,h) ≤ r+1/n.' In a symmetric metric, this implies p ∈ B(h, r+1/n), so Cn is contained in a single ball and hence bounded. In a weak metric with the paper's forward-ball convention B(p,r) = {q : d(p,q) ≤ r}, the inequality d(p,h) ≤ r+1/n places p in the reverse ball, not in the forward ball B(h, r+1/n), and no forward-ball containment follows. Thus the Heine-Borel hypothesis cannot be invoked for Cn. The paper's assertion that the proof 'did not use the symmetric property' is therefore false. Corollary 14 is load-bearing for the Funk weak-metric case in Corollary 19, so this is a central gap, not a presentation issue.","section":"3, Proposition 13 / Corollary 14"},{"comment":"The theorem claims that the topology induced by the Thompson metric coincides with the Euclidean topology on bounded convex domains, and the abstract advertises 'a proof that the topology induced by the Thompson metric coincides with the Hilbert.' The proof, however, cites a reference for the Hilbert metric and a reference for the Funk weak metric, but gives no argument or citation for the Thompson metric. Since Corollary 10's Heine-Borel property for Thompson spaces depends on this topology equivalence, and since this is one of the paper's stated contributions, the claim is unsupported as written.","section":"2, Theorem 9"},{"comment":"The proof of Lemma 23 refers to 'Case 3 of Lemma 22,' but Lemma 22 contains only Case 1 and Case 2. Moreover, the claimed O(log^3 m) running time for the basis computation relies entirely on an external three-point Hilbert-ball algorithm from reference [9] without stating its interface or the exact lemma being used. Since Theorem 24's O(n log^3 m) bound depends on these primitives, the algorithmic contribution is not self-contained and the internal reference is inconsistent.","section":"4, Lemma 23"}],"minor_comments":[{"comment":"The paper never defines 'bounded' for weak metric spaces, even though the Heine-Borel property is stated in terms of closed and bounded sets. In a non-symmetric space one must distinguish forward-bounded from reverse-bounded sets, and this distinction is precisely what is missing in Corollary 14.","section":"2, Definition 2 and Section 3"},{"comment":"The text says 'in the above proof of Theorem 13 we did not use the symmetric property'; the statement being proved is Proposition 13, not Theorem 13. Please correct the cross-reference.","section":"3, after Proposition 13"},{"comment":"The three-point Hilbert ball computation from [9] is referenced but not specified. For a self-contained algorithmic claim, at least state the exact result in [9] that provides an O(log^3 m) routine, or include the routine in the paper.","section":"4, Lemma 22"},{"comment":"The citation 'see Lemma 10 page 4' in reference [19] is imprecise; use a proper theorem/lemma number from the source.","section":"4, Lemma 21"}],"recommendation":"major_revision","confidential_remarks":"The core symmetric-metric result (Proposition 13 plus Theorem 16) is correct and could form the basis of a useful short paper. However, the advertised weak-metric generalization is not proven, the Thompson topology claim is missing its proof, and the algorithmic section relies on an internal cross-reference that does not exist. These are load-bearing issues for the paper's stated contributions. I would encourage the editor to invite a revision that either repairs these gaps or substantially narrows the claims, rather than reject outright, because the symmetric-metric portion is sound and the weak-metric counterexample is specific and potentially addressable with an added hypothesis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core reduction is right; the advertised weak-metric extension is not proven, and the algorithm section needs cleanup. I'd send it to review, expecting major revision.\n\nWhat's actually new: the observation that the Heine-Borel property guarantees the minimum ball property, and that the minimum ball property makes minimum-radius balls LP-type, is a clean and useful unifying statement. The application to Hilbert, Thompson, and Funk geometries is a sensible way to organize those problems, and the Hilbert two-point primitive (Lemma 21) is a concrete step toward an algorithm. The proof of Proposition 13 for symmetric metrics is fine, and the lexicographic tie-break in Theorem 16 is a nice way to make the LP-type function single-valued.\n\nThe soft spots are real. The stress-test note about Corollary 14 is correct: the boundedness step in Proposition 13 uses symmetry. In a weak metric, d(p,h) ≤ r+1/n does not put p in the forward ball B(h, r+1/n); it only puts p in the reverse ball. Under the standard definition of bounded (contained in some ball), C_n need not be bounded, so Heine-Borel cannot be applied. The paper explicitly says the proof 'did not use the symmetric property' — that's false. This gap undercuts the Funk case in Corollary 19 unless an extra hypothesis or a different boundedness argument is supplied.\n\nSecond, Theorem 9 is advertised as a proof that the Thompson topology coincides with the Hilbert topology, but the proof only cites results for Hilbert and Funk. The Thompson equivalence is asserted without a direct source or derivation, and Corollary 10 needs it.\n\nThird, the algorithm section has internal inconsistencies: Lemma 23 refers to 'Case 3 of Lemma 22,' which doesn't exist, and the O(log^3 m) three-point ball routine is cited from prior work rather than specified. That's acceptable practice, but the missing case reference undermines confidence. Minor: in the locality proof of Theorem 16, the inequality f(G∪{x}) ≤ f(G) is justified because B_G contains G∪{x}, not by monotonicity; the conclusion still holds.\n\nOverall: the central theorem is correct and worth having, and the applications are plausible, but the paper needs a repaired weak-metric argument, a real Thompson topology proof, and a cleaned-up Section 4. For readers working on LP-type problems or Hilbert geometry, it's worth reading; for referees, it deserves serious review rather than desk rejection.","headline":"Core Heine-Borel-to-LP-type theorem is correct; weak-metric extension and algorithm section need real repair before the paper can be trusted.","tokens_in":9188,"tokens_out":6218,"would_cite":false,"duration_ms":53137,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","52A20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that Heine-Borel metric spaces always have LP-type minimum enclosing balls, covering Hilbert, Thompson, and Funk geometries.","keywords":["Heine-Borel property","LP-type problems","minimum enclosing balls","Hilbert metric","Thompson metric","Funk weak metric","weak metric spaces","computational geometry"],"falsifier":"Take a bounded convex domain such as the open unit square, fix an interior point p, and test whether a Thompson ball of finite radius around p can contain a sequence of points approaching the boundary. If such a sequence exists, the closed bounded Thompson ball is not compact, so Heine-Borel fails and the LP-type conclusion for Thompson metrics collapses.","tokens_in":8190,"feed_emoji":"⚪","tokens_out":8963,"duration_ms":82293,"temperature":0.7,"pith_summary":"The paper establishes a common structural reason why \"smallest enclosing ball\" problems behave like linear programming: in any metric space where closed bounded sets are compact, the minimum-radius ball problem is LP-type. The proof is short and uses only existence of a smallest ball, which the Heine-Borel property guarantees. The paper then shows that Hilbert, Thompson, and Funk geometries on bounded convex domains all have this property, so their minimum-ball problems are all LP-type, including the asymmetric Funk weak metric when the ball direction is fixed. Along the way it argues that Thompson balls are equivalent to Hilbert balls up to a scaling factor, so the Thompson topology matches the Hilbert and Euclidean topologies. For the Hilbert case it supplies primitive operations and derives an O(n $log^{3}$ m) algorithm for n points inside an m-sided convex polygon.","feed_headline":"Smallest balls are LP-type in all Heine-Borel metric spaces","feed_subtitle":"The proof covers Hilbert, Thompson, and Funk geometries and yields an O(n log^3 m) Hilbert algorithm.","key_machinery":"The machinery is the LP-type framework applied to a minimum-radius-ball objective with a lexicographic tie-breaker. For a finite set H, define f(G) = inf{(r,p) : G ⊆ B(p,r)} with (r,p) ordered first by radius and then by a fixed ordering of centers, so every subset has a unique optimal ball. The Heine-Borel property enters through Proposition 13: for any finite H, the set of centers that enclose H at radius r + 1/n forms a decreasing sequence of closed bounded sets, whose nonempty intersection, by the nested-compact intersection theorem, contains a center for a ball of the infimal radius. For the non-Euclidean examples, the connecting fact is that Hilbert balls in a polygonal domain are convex polygons with O(m) sides constructible from spokes through vertices, and Thompson and Funk balls are defined by taking maxima or averages of directed Funk distances, so all three inherit the Euclidean topology on bounded convex domains.","core_discovery":"On its own terms, the central claim is Theorem 16: for any metric space satisfying the minimum ball property, and therefore any Heine-Borel metric space, the map from a finite point set to its lexicographically chosen minimum-radius enclosing ball defines an LP-type problem. The two defining properties, monotonicity and locality, follow because a minimum ball for a larger set covers every subset, and the chosen minimum ball is unique once centers are ordered. Corollary 17 extends the same argument to weak metric spaces, provided the distance direction is fixed when defining balls. Applied to bounded convex domains, the paper concludes that minimum-radius balls in the Hilbert metric and the Thompson metric are LP-type, and so are balls in the forward and reverse Funk weak metrics. The paper also claims that Thompson balls are Hilbert balls up to a scaling factor, and it gives concrete Hilbert-metric primitives: two-point centers in O(log m) time and three-point violation and basis operations in O($log^{3}$ m) time, leading to the O(n $log^{3}$ m) algorithm.","pith_inferences":["The same existence-only proof should apply to any metric or weak-metric space where finite sets have a minimum enclosing ball, even without Heine-Borel; the paper's discrete-metric example shows the condition is sufficient but not necessary.","The direction-fixing trick for weak metrics suggests that one-sided or directed versions of other geometric optimization problems may be LP-type under compactness conditions, not just minimum balls.","The O(n log^3 m) Hilbert algorithm assumes two black-box primitives from earlier work; a reader implementing the algorithm would need to supply those primitives or derive them directly from cross-ratio geometry.","Since the proof only needs compactness of closed bounded sets, other geodesic spaces with the Heine-Borel property would also inherit LP-type minimum-ball problems, such as the probability simplex with the Hilbert metric used in information geometry."],"forward_implications":["Every metric space with the Heine-Borel property automatically has an LP-type minimum-radius-ball problem, so randomized incremental algorithms with a constant-size basis apply without any additional geometric structure.","The Hilbert, Thompson, and Funk minimum-ball problems are all LP-type, extending the class of geometries where smallest enclosing balls can be solved by subexponential randomized algorithms.","For weak metric spaces, fixing the direction of the ball is sufficient; symmetry is not needed for the LP-type conclusion.","Hilbert minimum balls of n points in an m-sided convex polygon can be computed in O(n log^3 m) time using the paper's primitives.","Because Thompson balls are equivalent to Hilbert balls up to a scaling factor, Thompson metric minimum-ball computations can reuse Hilbert ball primitives."],"supporting_citations":[{"why":"Defines LP-type problems and gives the combinatorial bound that the algorithm's time bound builds on.","marker":"[26]"},{"why":"Supplies the LP-type primitive-operation framework and the Euclidean minimum-ball algorithm being generalized.","marker":"[17]"},{"why":"Gives the spoke construction and two-point Hilbert ball properties that the Hilbert primitives use.","marker":"[19]"},{"why":"Provides the three-point Hilbert ball algorithm and the combinatorial dimension assertion used for the O(log^3 m) primitives.","marker":"[9]"},{"why":"Cited for the claim that Hilbert metrics induce the Euclidean topology on bounded convex domains, supporting the Heine-Borel application.","marker":"[3]"},{"why":"Establishes Funk ball homotheties and Funk-metric topology facts used for Thompson balls and the Heine-Borel corollary.","marker":"[22]"},{"why":"Provides the nested compact intersection theorem, the compactness step that produces the minimum-radius center.","marker":"[25]"}],"fun_headline_variants":["LP-type min balls for Hilbert, Thompson, Funk metrics","Heine-Borel spaces guarantee LP-type minimum radius balls","Minimum balls are LP-type in Hilbert, Thompson, and Funk","LP-type property proven for min balls in weak metric spaces","From Heine-Borel to Hilbert: min balls are LP-type"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Thompson-metric result rests on the assertion that Thompson balls are equivalent to Hilbert balls, which makes the Thompson metric induce the Euclidean topology; that assertion is stated without a proof or direct citation in the paper.","fun_headline_variants_meta":{"raw":{"variants":["LP-type min balls for Hilbert, Thompson, Funk metrics","Heine-Borel spaces guarantee LP-type minimum radius balls","Minimum balls are LP-type in Hilbert, Thompson, and Funk","LP-type property proven for min balls in weak metric spaces","From Heine-Borel to Hilbert: min balls are LP-type"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000885,"raw_usage":{"total_tokens":3776,"prompt_tokens":854,"completion_tokens":2922,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":470,"completion_tokens_details":{"reasoning_tokens":2838}},"tokens_in":470,"tokens_out":2922,"duration_ms":19465,"temperature":1.0,"reasoning_tokens":2838,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:46:30.712409+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a bounded convex domain such as the open unit square, fix an interior point p, and test whether a Thompson ball of finite radius around p can contain a sequence of points approaching the boundary. If such a sequence exists, the closed bounded Thompson ball is not compact, so Heine-Borel fails and the LP-type conclusion for Thompson metrics collapses.","supporting_citations":[],"review_version":1}