Software for the Thompson and Funk Polygonal Geometry
Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, David M. Mount · 2025
Read Software for the Thompson and Funk Polygonal Geometry by Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, David M. Mount (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01988.txt.
Introduction
Hridhaan Banerjee and co-authors built teaching software for a family of exotic geometries defined inside convex polygons. These spaces, carrying the Thompson, Funk, reverse Funk, and Hilbert metrics, bend distance in ways unlike flat geometry, and they draw growing interest in computational geometry. The software lets users play with balls under these metrics inside a chosen polygon.
A companion program walks the user through the Hilbert geometry of a polygon. The authors aim at a double audience: students meeting these spaces for the first time, and researchers who need a hands-on tool to test ideas. The piece is presented as both an educational aid and research support.
Catalog record
| CREATOR | Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, David M. Mount |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 9 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-01988
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Software for the Thompson and Funk Polygonal Geometry Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, David M. Mount Abstract Metric spaces defined within convex polygons, such as the Thompson, Funk, reverse Funk, and Hilbert metrics, are subjects of recent exploration and study in computational geometry. This paper contributes an educational piece of software for understanding these unique geometries while also providing a tool to support their research. We provide dynamic software for manipulating the Funk, reverse Funk, and Thompson balls in convex polygonal domains. Additionally, we provide a visualization program for traversing the Hilbert polygonal geometry. Thomas Jefferson High School for Science and Technology, Virginia, USA and ~ [email protected] California State University Channel Islands, California, USA and ~ [email protected] Department of Computer Science, University of Maryland, College Park, USA and ~ [email protected]://orcid.org/0000-0002-5704-312X Mount Holyoke College, Massachusetts, USA and ~ [email protected] Montgomery Blair High School, Silver Spring, Maryland, USA and ~ [email protected] University of Maryland, College Park, USA and ~ [email protected] Department of Computer Science, University of Maryland, College Park, USA and ~ [email protected] Princeton University, New Jersey, USA and ~ [email protected] Department of Computer Science, University of Maryland, College Park, Maryland, USA and https://www.cs.umd.edu/~mount/ [email protected]://orcid.org/0000-0002-3290-8932 ccs Theory of computation Computational geometry keywords Thompson metric, Hilbert metric, Funk metric, balls † † runningtitle: Software for the Thompson and Funk Polygonal Geometry † † runningauthor: Banerjee, Day, Hunleth, Hwang, Gezalyan, Golovatskaia, Parepally, Wang, and Mount † † copyright: H. Banerjee, C. I. Day, M. Hunleth, S. Hwang, A. H. Gezalyan, O. Golovatskaia, N. Parepally, L. Wang, and D. Mount † † editors: Wolfgang Mulzer and Jeff M. Phillips † † event-title: 40th International Symposium on Computational Geometry (SoCG 2024) † † event-shorttitle: SoCG 2024 † † event-acronym: SoCG † † year: 2024 † † event-date: June 11-14, 2024 † † event-location: Athens, Greece † † event-logo: socg-logo.pdf † † series-volume: 293 † † articleno: 88 1 Introduction Thompson, Funk, reverse Funk, and Hilbert are closely related distance measures that apply to points in the interior of a convex body (see Section 2 for definitions). The Hilbert metric has applications in convex approximation [ 1 , 2 , 15 ] , real analysis [ 8 ] , linear algebra [ 9 ] , clustering [ 11 ] , and machine learning [ 14 ] and has been the subject of recent study for this reason [ 10 , 5 , 6 , 4 , 3 ] . The Funk, reverse Funk, and Thompson metrics are comparatively unexplored but all share similarities with the Hilbert metric [ 13 , 12 ] . In this paper, we present new dynamic software for manipulating the Funk, reverse Funk, and Thompson balls in convex polygonal domains. Additionally, we provide visualization software for traversing the Hilbert polygonal geometry. Our code is predominantly written in Javascript and is available at https://github.com/nithin1527/funk-geo-visualizer . To use the software, please go to https://funk-geo-visualizer.vercel.app/ . For more information on the usage, please see the README on the GitHub repository or watch the accompanying video available at https://www.youtube.com/watch?v=IeRIO25iK-o . 2 Definitions Throughout, \Omega refers to a convex polygon in \mathbb{R}^{2} with m sides. Let \partial\kern 1.0pt\Omega denote its boundary. When clear, we omit explicit reference to \Omega . Definition 1 (Funk weak metric) . Given two distinct points p,q\in\interior\Omega in \mathbb{R}^{d} , let q^{\prime} denote the intersection of the ray from p through q with \partial\kern 1.0pt\Omega . Define the Funk weak metric to be: F_{\Omega}(p,q)~=~\ln\frac{\|p-q^{\prime}\|}{\|q-q^{\prime}\|}, where F_{\Omega}(p,q)=0 . The above definition is also sometimes called the forward Funk metric . Note that the Funk weak metric is asymmetric. Its reverse, the \emph{reverseFunkmetric} , is defined to be rF_{\Omega}(p,q)=F_{\Omega}(q,p) . Define the Funk ball centered at a point p of radius r , denoted B_{F}(p,r) , to be the set of points q\in\interior\Omega such that F_{\Omega}(p,q)\leq r . The reverse Funk ball is defined analogously. These are scaled homotheties of \Omega (see Figure 1 (b) and (c)). Lemma 2 . The open forward Funk ball of radius r around a point p is the image of \Omega under Euclidean homothety around the point p with dilation factor of (1-e^{-r}) [ 12 ] . Lemma 3 . The open reverse Funk ball of radius r around a point p is the image of \Omega under Euclidean homothety around the point p with dilation factor of (e^{r}-1) [ 12 ] . The Hilbert metric can be defined as the average of the forward and reverse Funk metrics [ 12 ] . Figure 1: The Hilbert (a), Funk (b), Reverse Funk (c), and Thompson (d) balls around a point Definition 4 (Hilbert metric) . Given two distinct points p,q in a convex polygonal \Omega\subset\mathbb{R}^{d} we define the Hilbert metric to be: H_{\Omega}(p,q)~=~\frac{1}{2}(F_{\Omega}(p,q)+rF_{\Omega}(p,q)), Note that the Hilbert metric is a proper metric, obeying the identity of indiscernibles, symmetry, and the triangle inequality. Hilbert balls are polygons with at most 2m sides (see Figure 1 (a)). For a characterization of Hilbert balls see “Balls in the Hilbert Polygonal Geometry” by Nielsen and Shao [ 10 ] . The notion of the Hilbert metric gave rise to the definition of another metric by A.C. Thompson in 1963 called the Thompson metric [ 13 ] on convex cones. The formulation of this metric can be generalized through the Funk metric. Definition 5 (Thompson metric) . Given two distinct points p,q in a convex polygonal \Omega\subset\mathbb{R}^{d} we define the Thompson metric to be: T_{\Omega}(p,q)~=~\max(F_{\Omega}(p,q),rF_{\Omega}(p,q)), Note that the identity of indiscernibles and triangle inequality clearly carry over from the Funk metric. The symmetry of the Thompson metric follows from the fact that it is the maximum of the forward and reverse of a weak metric. The Thompson ball (see Figure 1 (d)) is the intersection of the forward and reverse Funk balls. Since both these balls are convex (as they are homotheties of \Omega intersected with \Omega [ 12 ] ), computing the Thompson ball reduces to calculating the intersection of two convex polygons. This can be done linearly in the complexity of the polygons. Hence, we get: Lemma 6 . The Thompson ball around a point p with radius r has at most 2m sides and is the intersection of the forward and reverse Funk balls around p with radius r . Thompson balls have an interesting property that sets them apart from many other metrics. Lemma 7 . Thompson balls are not pseudo-disks (see Figure 2 (a)). Lemma 8 . A Thomspon ball of radius r centered at p can be nested between two Hilbert balls of radius \frac{1}{2}r and r centered at p (see Figure 2 (b)). Proof. Given a convex body \Omega\subset\mathbb{R}^{d} , for every point p\in\Omega and radius 0<r , we will show: B_{H}(p,r/2)~\subset~B_{T}(p,r)~\subset~B_{H}(p,r). To prove that B_{T}(p,r)\subset B_{H}(p,r) , we must show that the Thompson distance from p to a point on the boundary of the ball is greater than or equal to the Hilbert. This follows directly from the definition of the Hilbert and Thompson metrics: H(a,b)~=~\frac{1}{2}(F(a,b)+F(b,a))\leq 2\cdot\frac{1}{2}(\max(F(a,b),F(b,a))=T(a,b). To prove that B_{H}(p,r/2)\subset B_{T}(p,r) , we must show that the Thompson distance from p to a point on the boundary of the ball is less than