Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry (Media Exposition)

Banerjee, Hridhaan; Brown, Soren; Cagan, June; Gezalyan, Auguste H.; Hunleth, Megan; Kailad, Veena; Kyoung, Chaewoon; Shigeno, Rowan; Tajeddin, Yasmine; Wagger, Andrew; Zhu, Kelin; Mount, David M.

doi:10.4230/LIPIcs.SoCG.2026.100

Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry

Hridhaan Banerjee Thomas Jefferson High School for Science and Technology, Alexandria, VA, USA Soren Brown Department of Computer Science, University of Maryland, College Park, MD, USA June Cagan Department of Computer Science, University of Maryland, College Park, MD, USA Auguste H. Gezalyan

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France Megan Hunleth Montgomery Blair High School, Silver Spring, MD, USA Veena Kailad Montgomery Blair High School, Silver Spring, MD, USA Chaewoon Kyoung Montgomery Blair High School, Silver Spring, MD, USA Rowan Shigeno Department of Mathematics, Haverford College, PA, USA Yasmine Tajeddin Department of Computer Science, University of Maryland, College Park, MD, USA Andrew Wagger Department of Computer Science, University of Maryland, College Park, MD, USA Kelin Zhu Department of Mathematics, University of Maryland, College Park, MD, USA David M. Mount

Department of Computer Science, University of Maryland, College Park, MD, USA

Abstract

Higher-order Voronoi diagrams and Delaunay mosaics in polygonal metrics have only recently been studied, yet no tools exist for visualizing them. We introduce a tool that fills this gap, providing dynamic interactive software for visualizing higher-order Voronoi diagrams and Delaunay mosaics along with clustering and tools for exploring overlap and outer regions in the Hilbert polygonal metric. We prove that $k^{th}$ order Voronoi cells are not always star-shaped and establish complexity bounds for our algorithm, which generates all order Voronoi diagrams at once. Our software unifies and extends previous tools for visualizing the Hilbert, Funk, and Thompson geometries.

Keywords and phrases:

Hilbert metric, Funk metric, Voronoi diagrams

Category:

Media Exposition

Copyright and License:

© Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth,
Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger,
Kelin Zhu, and David M. Mount; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Supplementary Material:

Software (Web Application): https://andrew.wagger.net/hilbert/ [3]

Audiovisual (Video): https://youtu.be/yhJn–3Qgks [4]

Funding:

REU-CAAR 2025

DOI:

10.4230/LIPIcs.SoCG.2026.100

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Hilbert metric has attracted recent interest due to its applications in clustering [17], non-linear embeddings [18], convex approximation [1, 2], and real analysis [14]. As such, there has been work on extending results from computational geometry to the Hilbert metric, such as Voronoi diagrams (including farthest-point Voronoi)[12, 9, 15], minimum enclosing balls [6], and Delaunay triangulations [11]. To aid in these endeavors, software to help visualize the Hilbert metric has been progressively developed. This began with a Hilbert ball visualizer [16], then some Voronoi demo software [9], which evolved into software for the Funk and Thomson polygonal geometry [5]. We build on this foundation by providing the first software with interactive support for dynamically visualizing higher-order Voronoi diagrams and Delaunay mosaics in the Hilbert metric, exploring overlap and outer regions (defined in Section 3), and step-by-step clustering on arbitrary convex polygonal domains. The software is implemented in JavaScript, it runs interactively in the browser, and it includes a tutorial video and brute force Voronoi mode for verification. It also maintains the features from all previous software.

2 Higher order structures

The study of $k^{th}$ order abstract Voronoi diagrams started with “On the complexity of higher order abstract Voronoi diagrams” where cells were determined by the $k$ closest sites [7]. The Hilbert metric does not immediately fall into the category of $k^{th}$ order abstract Voronoi diagrams, but can be made to fit it by extending bisectors to infinity without the extensions crossing. As such, there exist frameworks for efficient $k^{th}$ order Voronoi diagrams [8, 7]. Our visualization generates all orders at once using an edge labeling technique similar to those used in Euclidean geometry [10]. For completeness, we begin this section by proving two supporting lemmas that show our algorithm works. Then we present the algorithm. Throughout, we assume that we have been given some convex polygonal region $\Omega$ with $m$ sides and a set of $n$ sites $S$ . Both proofs use a classical technique using properties of balls [13].

Refer to caption — Figure 1: (a) First order Hilbert Voronoi (b) second order (c) final ( $(n-1)^{th}$ ) order.

Lemma 1.

The circumcenter of any three sites serves as a Voronoi vertex in both the $k^{th}$ and $(k+1)^{th}$ order Hilbert Voronoi diagrams for some $0<k<n-1$ .

Proof.

Consider the circumcenter of three sites $s_{1},s_{2},s_{3}$ lying on the boundary of ball $B$ , with $k-1$ sites of $S$ in the ball. Perturbing $B$ towards one of the sites will change which of $s_{1},s_{2},s_{3}$ is the $k^{th}$ closest site to the center of $B$ . Perturbing and growing the ball along one of the bisectors to include two sites will change which site is the $(k+1)^{st}$ closest. $\hfill\blacktriangleleft$

Lemma 2.

Every bisector path between circumcenters belongs to exactly one $k^{th}$ order cell.

Proof.

Consider the bisector between two sites $s_{1},s_{2}\in S$ lying on a $k^{th}$ -order cell. A ball moving along the bisector and passing through both sites contains exactly $k-1$ other sites before reaching a circumcenter with a third site. Perturbing the ball off the bisector causes it to include either $s_{1}$ or $s_{2}$ , shifting the center into the $k^{{th}}$ order cell of one or the other. $\hfill\blacktriangleleft$

Our algorithm proceeds in three phases: Preprocessing computes all pairwise bisectors and all three site circumcenters parametrized along their respective bisectors. Looping over the bisectors lets us determine the diagram containment of the first bisector portion by checking the distance to each site. Traversing the bisector and updating diagram containment at each circumcenter yields a labeling of each bisector portion by the degree-order Hilbert Voronoi diagram it is part of, allowing us to display it quickly based on user input.

In the following we implicitly use three facts from [11, 12]; first, we can order the boundary of $\Omega$ to calculate Hilbert distances in time $O(\log m)$ , second we can order the boundary of $\Omega$ to calculate circumcenters in time $O(\log^{3}m)$ , and third, bisectors have complexity $O(m)$ .

Corollary 3.

Our algorithm takes time $O(n^{2}m\log m+n^{3}\log^{3}m+n^{3}\log n\log m)$ with space $O(m\log m+n^{3}+n^{2}m)$ .

Proof.

Preprocessing takes $O(n^{2}m\log m)$ time to compute all bisectors and $O(n^{3}\log^{3}m)$ time for computing all circumcenters (which we bucket by bisector). Sorting the circumcenters along the bisectors in the buckets takes $O(n^{3}\log n)$ .

We determine the containment of the first bisector component in $O(n\log n\log m)$ time per bisector. Then, we traverse the bisector, determining the containment of each vertex and each bisector segment in $O(n)$ time, since there are $O(n)$ circumcenters along each bisector. Since we do this for all $n^{2}$ bisectors, this takes $O(n^{2}(n\log n\log m+n))$ . Our final runtime is $O(n^{2}m\log m+n^{3}\log^{3}m+n^{3}\log n\log m)$ .

The storage consists of $O(m\log m)$ to order the boundary, $O(n^{3})$ for circumcenters ordered along bisectors, and $O(n^{2}m)$ for the bisectors, giving us $O(m\log m+n^{3}+n^{2}m)$ storage. $\hfill\blacktriangleleft$

Observation 4.

In the Hilbert metric, $k^{th}$ order Voronoi cells are not always star-shaped, a star-shaped region has an interior point from which all others are visible via a segment.

Proof.

This can be seen with the following $\Omega$ : a square with coordinates from (100, 100) to (300, 300) and sites at (160, 284.9), (140, 170), (130, 165), (180, 285). The second-order Voronoi generates a non-star-shaped region. This configuration is in general position. $\hfill\blacktriangleleft$

We leverage our results on $k^{th}$ -order cells to compute the Delaunay mosaic by computing a modified Fréchet mean (a point that minimizes the sum of distances) of the sites of each cell, and connecting them if their cells are adjacent.

3 Overlap and Outer Region

One notable property of the Hilbert metric is that three sites do not always have a circumcenter [9]. First we recall what it means to be a ball at infinity through two sites [11]. Then we define the overlap and outer regions which characterize circumcenter existence.

Definition 5 (Infinite Ball).

Given two sites $s_{1},s_{2}\in S$ , consider balls passing through them with centers along the bisector parametrized by $t\in[0,1]$ . This yields two limit balls on the boundary of $\Omega$ : $B_{0}(p\,:\,q)$ at $t=0$ and $B_{1}(p\,:\,q)$ at $t=1$ . (See Figure 3.)

Definition 6 (Overlap Region).

Given two sites $s_{1},s_{2}\in S$ , their overlap region, denoted $Z(p,q)$ , is $B_{0}(p\,:\,q)\cap B_{1}(p\,:\,q)$ .

Definition 7 (Outer Region).

Given two sites $s_{1},s_{2}\in S$ , their outer region, denoted $W(p,q)$ , is $\operatorname{int}\Omega-\left(B_{0}(p\,:\,q)\cup B_{1}(p\,:\,q)\right)$ .

The overlap is the region between two sites $s_{1}$ , $s_{2}$ where there is no circumcenter between $s_{1}$ , $s_{2}$ , and $p$ [11]. The outer region is the region that is not between the two sites where there is no circumcenter. In our software, we give users the option to display these regions dynamically. Users can generate these regions for any two sites, then move a third site between them to observe the behavior of the bisectors of the three sites.

4 Clustering

In 2019, Nielsen and Sun introduced clustering in the Hilbert simplex [17]. We expand on this by allowing users to interactively visualize clustering on arbitrary Hilbert polygonal geometries. We provide $k$ -means and single linkage clustering (see Figure 4).

5 Conclusion

We have introduced the first software for visualizing higher-order Voronoi diagrams, Delaunay mosaics, clustering, overlap and outer regions in arbitrary convex Hilbert polygonal geometries.

References

[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, 2024. doi:10.1137/1.9781611977936.26.
[3] Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry. Software (visited on 2026-05-12). URL: https://andrew.wagger.net/hilbert/, doi:10.4230/artifacts.25998.
[4] Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry. Audiovisual (visited on 2026-05-12). URL: https://youtu.be/yhJn--3Qgks, doi:10.4230/artifacts.25999.
[5] Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, and David M. Mount. Software For the Thompson and Funk Geometry. doi:10.4230/artifacts.23291.
[6] Hridhaan Banerjee, Carmen Isabel Day, Megan Hunleth, Sarah Hwang, Auguste H Gezalyan, Olya Golovatskaia, Nithin Parepally, Lucy Wang, and David M Mount. On the heine-borel property and minimum enclosing balls. arXiv preprint arXiv:2412.17138, 2024. doi:10.48550/arXiv.2412.17138.
[7] Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, and Maksym Zavershynskyi. On the complexity of higher order abstract voronoi diagrams. Computational Geometry, 48(8):539–551, 2015. doi:10.1016/j.comgeo.2015.04.008.
[8] Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. An efficient randomized algorithm for higher-order abstract voronoi diagrams. Algorithmica, 81(6):2317–2345, 2019. doi:10.1007/S00453-018-00536-7.
[9] Madeline Bumpus, Caesar Dai, Auguste H. Gezalyan, Sam Munoz, Renita Santhoshkumar, Songyu Ye, and David M. Mount. Analysis of dynamic voronoi diagrams in the hilbert metric. Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023) Montreal, Canada, 2023.
[10] Mercè Claverol, Andrea de las Heras Parrilla, Clemens Huemer, and Alejandra Martínez-Moraian. The edge labeling of higher order voronoi diagrams. Journal of Global Optimization, 90(2):515–549, 2024. doi:10.1007/S10898-024-01386-0.
[11] Auguste H. Gezalyan, Soo H. Kim, Carlos Lopez, Daniel Skora, Zofia Stefankovic, and David M. Mount. Delaunay Triangulations in the Hilbert Metric. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SWAT.2024.25.
[12] Auguste H. Gezalyan and David M. Mount. Voronoi diagrams in the Hilbert metric. In 39th International Symposium on Computational Geometry (SoCG 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.SoCG.2023.35.
[13] Der-Tsai Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE transactions on computers, 100(6):478–487, 1982. doi:10.1109/TC.1982.1676031.
[14] Bas Lemmens and Roger D. Nussbaum. Birkhoff’s version of hilbert’s metric and its applications in analysis, December 2014. doi:10.4171/147-1/10.
[15] Mook Kwon Jung Minju Song and Hee-Kap Ah. Farthest-point voronoi diagrams in the hilbert metric. In Proceedings of the 19th Algorithms and Data Structures Symposium (WADS 2025), 2025.
[16] Frank Nielsen and Laetitia Shao. On balls in a Hilbert polygonal geometry (multimedia contribution). In Proc. 33rd Internat. Sympos. Comput. Geom., volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1–67:4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.SoCG.2017.67.
[17] Frank Nielsen and Ke Sun. Clustering in Hilbert’s projective geometry: The case studies of the probability simplex and the elliptope of correlation matrices. In Frank Nielsen, editor, Geometric Structures of Information, pages 297–331. Springer Internat. Pub., 2019. doi:10.1007/978-3-030-02520-5_11.
[18] Frank Nielsen and Ke Sun. Non-linear embeddings in Hilbert simplex geometry. In Topological, Algebraic and Geometric Learning Workshops 2023, pages 254–266. PMLR, 2023. URL: https://proceedings.mlr.press/v221/nielsen23a.html.

[bib.bib1] [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.

[bib.bib2] [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, 2024. doi:10.1137/1.9781611977936.26.

[bib.bib3] [3] Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry. Software (visited on 2026-05-12). URL: https://andrew.wagger.net/hilbert/, doi:10.4230/artifacts.25998.

[bib.bib4] [4] Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry. Audiovisual (visited on 2026-05-12). URL: https://youtu.be/yhJn--3Qgks, doi:10.4230/artifacts.25999.

[bib.bib5] [5] Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, and David M. Mount. Software For the Thompson and Funk Geometry. doi:10.4230/artifacts.23291.

[bib.bib6] [6] Hridhaan Banerjee, Carmen Isabel Day, Megan Hunleth, Sarah Hwang, Auguste H Gezalyan, Olya Golovatskaia, Nithin Parepally, Lucy Wang, and David M Mount. On the heine-borel property and minimum enclosing balls. arXiv preprint arXiv:2412.17138, 2024. doi:10.48550/arXiv.2412.17138.

[bib.bib7] [7] Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, and Maksym Zavershynskyi. On the complexity of higher order abstract voronoi diagrams. Computational Geometry, 48(8):539–551, 2015. doi:10.1016/j.comgeo.2015.04.008.

[bib.bib8] [8] Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. An efficient randomized algorithm for higher-order abstract voronoi diagrams. Algorithmica, 81(6):2317–2345, 2019. doi:10.1007/S00453-018-00536-7.

[bib.bib9] [9] Madeline Bumpus, Caesar Dai, Auguste H. Gezalyan, Sam Munoz, Renita Santhoshkumar, Songyu Ye, and David M. Mount. Analysis of dynamic voronoi diagrams in the hilbert metric. Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023) Montreal, Canada, 2023.

[bib.bib10] [10] Mercè Claverol, Andrea de las Heras Parrilla, Clemens Huemer, and Alejandra Martínez-Moraian. The edge labeling of higher order voronoi diagrams. Journal of Global Optimization, 90(2):515–549, 2024. doi:10.1007/S10898-024-01386-0.

[bib.bib11] [11] Auguste H. Gezalyan, Soo H. Kim, Carlos Lopez, Daniel Skora, Zofia Stefankovic, and David M. Mount. Delaunay Triangulations in the Hilbert Metric. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SWAT.2024.25.

[bib.bib12] [12] Auguste H. Gezalyan and David M. Mount. Voronoi diagrams in the Hilbert metric. In 39th International Symposium on Computational Geometry (SoCG 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.SoCG.2023.35.

[bib.bib13] [13] Der-Tsai Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE transactions on computers, 100(6):478–487, 1982. doi:10.1109/TC.1982.1676031.

[bib.bib14] [14] Bas Lemmens and Roger D. Nussbaum. Birkhoff’s version of hilbert’s metric and its applications in analysis, December 2014. doi:10.4171/147-1/10.

[bib.bib15] [15] Mook Kwon Jung Minju Song and Hee-Kap Ah. Farthest-point voronoi diagrams in the hilbert metric. In Proceedings of the 19th Algorithms and Data Structures Symposium (WADS 2025), 2025.

[bib.bib16] [16] Frank Nielsen and Laetitia Shao. On balls in a Hilbert polygonal geometry (multimedia contribution). In Proc. 33rd Internat. Sympos. Comput. Geom., volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1–67:4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.SoCG.2017.67.

[bib.bib17] [17] Frank Nielsen and Ke Sun. Clustering in Hilbert’s projective geometry: The case studies of the probability simplex and the elliptope of correlation matrices. In Frank Nielsen, editor, Geometric Structures of Information, pages 297–331. Springer Internat. Pub., 2019. doi:10.1007/978-3-030-02520-5_11.

[bib.bib18] [18] Frank Nielsen and Ke Sun. Non-linear embeddings in Hilbert simplex geometry. In Topological, Algebraic and Geometric Learning Workshops 2023, pages 254–266. PMLR, 2023. URL: https://proceedings.mlr.press/v221/nielsen23a.html.