Software for the Thompson and Funk Polygonal Geometry (Media Exposition)

Hridhaan Banerjee, C. T. Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Lu Wang, David M. Mount

TL;DR

Researchers have released a new suite of open-source tools to visualize and manipulate "exotic" non-Euclidean metrics—specifically the Funk, Thompson, and Hilbert metrics—within convex polygons. This software bridges the gap between abstract geometric theory and intuitive understanding, offering a dynamic way to explore how distance behaves when the "straight line" is dictated by the boundaries of a shape.

What Problem Does This Paper Address?

In standard Euclidean geometry, a "ball" is always a circle or sphere. However, in computational geometry, researchers often work with metrics defined relative to a convex container (a "domain"). Metrics like the Hilbert metric have found niches in machine learning, clustering, and convex approximation, but others—like the Funk and Thompson metrics—remain relatively unexplored.

The challenge is that these metrics are mathematically "weird." The Funk metric is asymmetric (the distance from $A$ to $B$ isn't the same as $B$ to $A$), and the shapes of "balls" in these spaces change drastically based on where you are relative to the container's boundary. This paper addresses the lack of accessible visualization tools, providing a way for students and researchers to build intuition for these complex geometric structures.

Methods

The authors developed a web-based suite called the Funk-Geo-Visualizer, primarily written in JavaScript. The software handles several key tasks:

  1. Ball Manipulation: It allows users to dynamically generate and move "balls" (sets of points within a certain distance of a center) for Funk, reverse Funk, and Thompson metrics.
  2. Geometric Computation: To render Thompson balls, the software calculates the intersection of two convex polygons (the forward and reverse Funk balls), a process that runs in linear time relative to the number of sides of the container.
  3. Projective Traversal: To simulate "moving" through a Hilbert geometry, the authors implemented a projective mapping ($\phi_v$). Because moving toward a boundary can "squash" the geometry into extremely skinny shapes, they use an approximate John ellipsoid (the largest ellipsoid that fits inside a convex body) and Cholesky decomposition to normalize the view, ensuring the user stays centered and the geometry remains readable.

Datasets

Not discussed in the paper. As this is a software and theory exposition, it does not rely on external datasets for training or evaluation.

Key Insights and Ideas

  • The "Not-a-Disk" Surprise: One of the most striking insights is that Thompson balls are not pseudo-disks. In many geometries, two balls of the same type will intersect in a simple, well-behaved way. Thompson balls can intersect in much more complex patterns, which has significant implications for algorithms that rely on "well-behaved" distance functions.
  • Homothety and Intersections: The paper highlights that Funk balls are simply "scaled-down" versions (homotheties) of the original container. A Thompson ball is the intersection of a forward Funk ball and a reverse Funk ball.
  • The Nesting Lemma: The authors provide a formal proof that a Thompson ball of radius $r$ is always "sandwiched" between two Hilbert balls (one of radius $r/2$ and one of radius $r$). This provides a concrete mathematical link between these different ways of measuring distance.

Key Results

  • Software Release: The primary result is the availability of the funk-geo-visualizer, an interactive tool for exploring these geometries.
  • Complexity Bounds: The authors confirm that for a container with $m$ sides, the resulting Hilbert and Thompson balls are polygons with at most $2m$ sides.
  • Visualization of Traversal: The tool successfully demonstrates "travelling" inside a polygon (like a hendecagon or a square) while maintaining a stable perspective through projective transformations, effectively turning abstract metric theory into a first-person navigation experience.

Limitations and Future Work

The authors note that the projective mapping used for traversal can deform the domain into "very skinny forms." While they mitigate this using the John ellipsoid method to re-center and normalize the view, this remains a computational hurdle for highly complex or irregular polygons.

While the current software focuses on 2D polygonal domains, future work could potentially extend these visualizations to higher dimensions or non-polygonal convex bodies, where the boundary math becomes significantly more complex.

Summary updated

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.
BibTeX
@misc{banerjee2025software,
  author = {Hridhaan Banerjee and C. T. Day and Auguste H. Gezalyan and Olga Golovatskaia and Megan Hunleth and Sarah Hwang and Nithin Parepally and Lucy Lu Wang and David M. Mount},
  title = {{Software for the Thompson and Funk Polygonal Geometry (Media Exposition)}},
  year = {2025},
  eprint = {2503.01988},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.01988},
}
Figure