This repo is our first proof of concept and is superseded by improved version funk-geo-visualizer:)

Table of Contents

• Overview
• Installation
• Run
• Acknowledgement
• Citing this Work
• License

A dynamic visualization software for Voronoi diagrams in the Hilbert metric on user specified convex polygons.

Overview

In 1895, Hilbert introduced the Hilbert metric which defines a distance function on the interior of any convex body $K\subset \mathbb{RP}^d$. Hilbert geometry generalize hyperbolic geometry by adapting the Cayley-Klein model of hyperbolic geometry (on Euclidean balls) to any convex body. The Hilbert metric is a projective metric invariant under collineations of $\mathbb{RP}^d$. Hilbert geometry provides new insights into classical questions from convexity theory and the study of metric and differential geometries (such as Finsler geometries).

Hilbert geometry is particularly valuable in the field of convex approximation. Efficient approximations of convex bodies have been used in a wide range of applications, including approximate nearest neighbor searching both in Euclidean space and more general metrics, optimal construction of ε-kernels, solving the closest vector problem approximately, and computing approximating polytopes with low combinatorial complexity. These works all share one thing in common they approximate a convex body by covering it with elements that behave like metric balls. These covering elements go under various names: Macbeath regions, Macbeath ellipsoids, Dikin ellipsoids, and $(2,ε)$-covers. While these all behave like metric balls, the question is in what metric space? Abdelkader and Mount showed that these shapes are, up to constant factors, equivalent to Hilbert balls. Thus, a deeper understanding of geometry within the Hilbert metric can lead in a principled way to a deeper understanding of convex approximation.

As a part of the paper, we built this software to help visualize Voronoi diagrams in the Hilbert metric on user specified convex polygons.

To read our full paper, please check out our arXiv: Software and Analysis for Dynamic Voronoi Diagrams in the Hilbert Metric

Installation

Download the latest release through the release tab

To edit the source code on your local machine you need Java8 and processing2.2.1

Run

Simply double click the "HilbertVoronoi.jar" icon or navigate to the directory that contains the jar file and run the below command

java -jar HilbertVoronoiv0.1.0-alpha.jar

You should see below window when launched successfully

Acknowledgement

We would like to thank Frank Nielsen and Laëtitia Shao for sharing their Hilbert Ball source code with us.

Citing this Work

@article{Gezalyan2021VoronoiDI,
  title={Voronoi Diagrams in the Hilbert Metric},
  author={Auguste H. Gezalyan and David M. Mount},
  journal={ArXiv},
  year={2021},
  volume={abs/2112.03056}
}

License

MIT