Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

On The Heine-Borel Property and Minimum Enclosing Balls

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

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

Pith's one-line read This paper proves that Heine-Borel metric spaces always have LP-type minimum enclosing balls, covering Hilbert, Thompson, and Funk geometries.

desk verdict Core Heine-Borel-to-LP-type theorem is correct; weak-metric extension and algorithm section need real repair before the paper can be trusted. read the letter →

arxiv 2412.17138 v2 pith:LRLHOMBK submitted 2024-12-22 cs.CG math.MG

Hridhaan Banerjee , Carmen Isabel Day , Megan Hunleth , Sarah Hwang , Auguste H. Gezalyan , Olya Golovatskaia , Nithin Parepally , Lucy Wang
show 1 more author
David M. Mount
This is my paper · ORCID
classification cs.CGmath.MG MSC 68U0552A20
keywords Heine-BorelpropertyLP-typeproblemsminimumenclosingballsHilbertmetricThompsonFunkweakspacescomputationalgeometry
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [3, Proposition 13 / Corollary 14] 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.
  2. [2, Theorem 9] 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.
  3. [4, Lemma 23] 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.
minor comments (4)
  1. [2, Definition 2 and Section 3] 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.
  2. [3, after Proposition 13] 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.
  3. [4, Lemma 22] 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.
  4. [4, Lemma 21] The citation 'see Lemma 10 page 4' in reference [19] is imprecise; use a proper theorem/lemma number from the source.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central Heine-Borel/LP-type theorem is proved directly from definitions, and the Section 4 self-citations are external algorithmic tools rather than inputs recycled as outputs.

full rationale

The main derivation chain is self-contained. Proposition 13 proves the minimum ball property from the Heine-Borel property using a decreasing nested sequence of closed, bounded sets C_n, and Theorem 16 verifies the LP-type axioms (monotonicity and locality) directly from the definition of f as a lexicographic infimum over enclosing balls. No parameter is fitted, no normalization is hidden, and no equation is defined in terms of its own conclusion; the LP-type conclusion is not a restatement of the minimum ball property, since locality is established by an argument, not by definition. The weak-metric extension (Corollary 14) is not circular, but it is unsupported as written: the boundedness assertion 'Each C_n is bounded since for any h∈H and any p∈C_n, d(p,h)≤r+1/n' uses symmetry to move the center to h, whereas Definition 2 defines only forward balls B(p,r) = {q : d(p,q)≤r}; this is a correctness gap, not a circular reduction. Theorem 9's Thompson topology claim is likewise asserted without a direct citation or proof, and Lemma 23 refers to a nonexistent 'Case 3' of Lemma 22, but these are missing-support issues. Section 4 relies on prior work by overlapping authors, especially [9] for the O(log^3 m) three-point Hilbert ball routine and [4] for bisectors; those are external published results used as building blocks, not conclusions derived from the present paper's premises, so they do not make the derivation circular. Overall, no load-bearing step reduces to its own input, and the central theorem retains independent content.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central theorem uses only standard set-theoretic tools and the definition of LP-type. The applications depend on cited topology results and on previously published Hilbert-geometry algorithms. No free parameters are fitted and no new entities are postulated.

assumptions (6)
  • standard math Cantor's intersection theorem for decreasing nested compact sets
    Used in Proposition 13 to show the intersection of the center sets Cn is nonempty.
  • standard math Every set can be well-ordered
    The definition of f in Theorem 16 uses a well-ordering of X to make infima unique; Proposition 18 replaces this with the lexicographic order on R^k.
  • domain assumption Hilbert, Thompson, and Funk metrics induce the Euclidean topology on bounded convex domains
    Theorem 9 states this and cites references for Hilbert and Funk, but the Thompson case is asserted without proof. This is used to establish the Heine-Borel property in Corollary 10.
  • domain assumption Hilbert balls in a convex polygon have O(m) sides and the combinatorial dimension of the minimum Hilbert ball problem is 3
    Lemmas 6 and 20 rely on prior results by Nielsen-Shao [19] and Gezalyan et al. [9].
  • domain assumption The three-point minimum Hilbert ball can be computed in O(log^3 m) time using the algorithm of [9]
    Used in Lemmas 22 and 23 for the violation test and basis computation; this is a tooling assumption passed to a cited paper.
  • domain assumption The two-point minimum Hilbert ball center lies on a line segment of the bisector between the two points
    Lemma 21 cites [4,19] for the bisector structure and uses binary search on the boundary, relying on that cited structure.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On The Heine-Borel Property and Minimum Enclosing Balls." pith.science (2026). https://pith.science/paper/LRLHOMBK

@misc{pith2026241217138,
  author       = {Pith},
  title        = {Pith review of: On The Heine-Borel Property and Minimum Enclosing Balls},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LRLHOMBK}},
  note         = {Machine review of arXiv:2412.17138}
}
read the original abstract

In this paper, we contribute a proof that minimum radius balls over metric spaces with the Heine-Borel property are always LP type. Additionally, we prove that weak metric spaces, those without symmetry, also have this property if we fix the direction in which we take their distances from the centers of the balls. We use this to prove that the minimum radius ball problem is LP type in the Hilbert and Thompson metrics and Funk weak metric. In doing so, we contribute a proof that the topology induced by the Thompson metric coincides with the Hilbert. We provide explicit primitives for computing the minimum radius ball in the Hilbert metric.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Hilbert geometry of the symmetric positive-definite bicone: Application to the geometry of the extended Gaussian family

    cs.CG 2025-08 conditional novelty 6.0 of 10

    A closed-form Hilbert distance on the matrix box {0 ≺ X ≺ I} (the extended Gaussian parameter space) is derived, plus a claimed full isometry classification: orthogonal conjugation and complement X → I−X.

Reference graph

Works this paper leans on

16 extracted references · 8 canonical work pages · cited by 1 Pith paper

  1. [1]

    1 Ahmed Abdelkader and David M. Mount. Economical Delone sets for approximating convex bodies. In Proc. 16th Scand. Workshop Algorithm Theory, pages 4:1–4:12, 2018.doi:10.4230/ LIPIcs.SWAT.2018.4. 2 Ahmed Abdelkader and David M Mount. Convex approximation and the Hilbert geometry. In 2024 Symposium on Simplicity in Algorithms (SOSA), pages 286–298. SIAM,

    work page 2018

  2. [11]

    From Funk to Hilbert geometry

    22 Athanase Papadopoulos and Marc Troyanov. From Funk to Hilbert geometry. InHandbook of Hilbert geometry, volume 22 ofIRMA Lectures in Mathematics and Theoretical Physics, pages 33–68. European Mathematical Society Publishing House, 2014.doi:10.4171/147-1/2. 23 Athanase Papadopoulos and Marc Troyanov.Handbook of Hilbert geometry, volume 22 of IRMA Lectur...

    doi:10.4171/147-1/2 2014

  3. [12]

    24 David Reeb, Michael J

    doi:10.4171/147. 24 David Reeb, Michael J. Kastoryano, and Michael M. Wolf. Hilbert’s projective metric in quantum information theory.J. Math. Physics, 52(8),

    doi:10.4171/147

  4. [16]

    Flag-approximability of convex bodies and volume growth of Hilbert geometries

    29 Constantin Vernicos and Cormac Walsh. Flag-approximability of convex bodies and volume growth of Hilbert geometries, 2018.arXiv:1809.09471. 30 Robert Williamson and Ludvik Janos. Constructing metrics with the Heine-Borel property. Proceedings of the American Mathematical Society, 100(3):567–573, 1987

    work page Pith review arXiv 2018

  5. [1895]

    13 Bas Lemmens and Roger Nussbaum

    doi:10.1007/BF02096204. 13 Bas Lemmens and Roger Nussbaum. Birkhoff’s version of Hilbert’s metric and its applications in analysis,

    doi:10.1007/bf02096204

  6. [1929]

    Gezalyan, Soo H

    9 Auguste H. Gezalyan, Soo H. Kim, Carlos Lopez, Daniel Skora, Zofia Stefankovic, and David M. Mount. Delaunay triangulations in the hilbert metric. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Schloss Dagstuhl–Leibniz-Zentrum für Informatik,

    work page 2024

  7. [1963]

    Funk and Hilbert geometries from the Finslerian Viewpoint

    28 Marc Troyanov. Funk and Hilbert geometries from the Finslerian viewpoint.arXiv preprint arXiv:1311.2508,

    work page Pith review arXiv

  8. [1964]

    A combinatorial bound for linear programming and related problems

    26 Micha Sharir and Emo Welzl. A combinatorial bound for linear programming and related problems. In STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992 Proceedings 9, pages 567–579. Springer,

    work page 1992

Show all 16 references
  1. [2011]

    25 Walter Rudin et al.Principles of mathematical analysis, volume

    doi:10.1063/1.3615729. 25 Walter Rudin et al.Principles of mathematical analysis, volume

    doi

  2. [2013]

    14 Bas Lemmens and Mark Roelands

    arXiv:1304.7921. 14 Bas Lemmens and Mark Roelands. Unique geodesics for Thompson’s metric.Annales de l’Institut Fourier, 65(1):315–348,

    arXiv

  3. [2014]

    Volume growth of Funk geometry and the flags of polytopes.arXiv preprint arXiv:2306.09268,

    7 Dmitry Faifman, Constantin Vernicos, and Cormac Walsh. Volume growth of Funk geometry and the flags of polytopes.arXiv preprint arXiv:2306.09268,

  4. [2016]

    6 Ştefan Cobzaş and Mircea-Dan Rus

    doi:10.1137/16M1061382. 6 Ştefan Cobzaş and Mircea-Dan Rus. Normal cones and Thompson metric.Topics in Mathe- matical Analysis and Applications, pages 209–258,

    doi

  5. [2017]

    10 On The Heine-Borel Property and Minimum Enclosing Balls 20 Frank Nielsen and Ke Sun

    (Multimedia contribution).doi: 10.4230/LIPIcs.SoCG.2017.67. 10 On The Heine-Borel Property and Minimum Enclosing Balls 20 Frank Nielsen and Ke Sun. Clustering in Hilbert’s projective geometry: The case studies of the probability simplex and the elliptope of correlation matrice...

    2017 doi

  6. [2019]

    21 Frank Nielsen and Ke Sun

    doi: 10.1007/978-3-030-02520-5_11. 21 Frank Nielsen and Ke Sun. Non-linear embeddings in Hilbert simplex geometry. InTopological, Algebraic and Geometric Learning Workshops 2023, pages 254–266. PMLR,

    2023 doi

  7. [2023]

    5 Yongxin Chen, Tryphon Georgiou, and Michele Pavon

    arXiv:2304.02745. 5 Yongxin Chen, Tryphon Georgiou, and Michele Pavon. Entropic and displacement interpolation: A computational approach using the Hilbert metric.SIAM J. Appl. Math., 76:2375–2396,

    arXiv

  8. [2024]

    Gezalyan and David M

    10 Auguste H. Gezalyan and David M. Mount. Voronoi diagrams in the Hilbert metric. In39th International Symposium on Computational Geometry (SoCG 2023). Schloss Dagstuhl-Leibniz- Zentrum für Informatik,

    2023

Pith tools

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