3 Search Results for "Shao, Laetitia"

Document
DOI: 10.4230/LIPIcs.WADS.2025.48
Farthest-Point Voronoi Diagrams in the Hilbert Metric

Authors: Minju Song, Mook Kwon Jung, and Hee-Kap Ahn

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
The Hilbert metric, introduced by David Hilbert in 1895, is a projective metric defined on a bounded convex domain in a Euclidean space. For a convex polygon with m vertices and n point sites lying inside the polygon in the plane, it is shown that the nearest-point Voronoi diagram in the Hilbert metric has combinatorial complexity of O(mn) [Gezalyan and Mount, SoCG 2023]. In this paper, we show that the farthest-point Voronoi diagram in the Hilbert metric has combinatorial complexity O(m), which is independent of the number of sites. Also, we present an efficient algorithm to compute the farthest-point Voronoi diagram.
Cite as

Minju Song, Mook Kwon Jung, and Hee-Kap Ahn. Farthest-Point Voronoi Diagrams in the Hilbert Metric. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{song_et_al:LIPIcs.WADS.2025.48,
  author =	{Song, Minju and Jung, Mook Kwon and Ahn, Hee-Kap},
  title =	{{Farthest-Point Voronoi Diagrams in the Hilbert Metric}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.48},
  URN =		{urn:nbn:de:0030-drops-242797},
  doi =		{10.4230/LIPIcs.WADS.2025.48},
  annote =	{Keywords: Farthest-point Voronoi diagram, Hilbert metric, Complexity, Algorithm}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.82
Software for the Thompson and Funk Polygonal Geometry (Media Exposition)

Authors: Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, and David M. Mount

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

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.
Cite as

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 Polygonal Geometry (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 82:1-82:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.SoCG.2025.82,
  author =	{Banerjee, Hridhaan and Day, Carmen Isabel and Gezalyan, Auguste H. and Golovatskaia, Olga and Hunleth, Megan and Hwang, Sarah and Parepally, Nithin and Wang, Lucy and Mount, David M.},
  title =	{{Software for the Thompson and Funk Polygonal Geometry}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{82:1--82:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.82},
  URN =		{urn:nbn:de:0030-drops-232349},
  doi =		{10.4230/LIPIcs.SoCG.2025.82},
  annote =	{Keywords: Thompson metric, Hilbert metric, Funk metric, balls}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.67
On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution)

Authors: Frank Nielsen and Laetitia Shao

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Hilbert geometry is a metric geometry that extends the hyperbolic Cayley-Klein geometry. In this video, we explain the shape of balls and their properties in a convex polygonal Hilbert geometry. First, we study the combinatorial properties of Hilbert balls, showing that the shapes of Hilbert polygonal balls depend both on the center location and on the complexity of the Hilbert domain but not on their radii. We give an explicit description of the Hilbert ball for any given center and radius. We then study the intersection of two Hilbert balls. In particular, we consider the cases of empty intersection and internal/external tangencies.
Cite as

Frank Nielsen and Laetitia Shao. On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 67:1-67:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nielsen_et_al:LIPIcs.SoCG.2017.67,
  author =	{Nielsen, Frank and Shao, Laetitia},
  title =	{{On Balls in a Hilbert Polygonal Geometry}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{67:1--67:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.67},
  URN =		{urn:nbn:de:0030-drops-72443},
  doi =		{10.4230/LIPIcs.SoCG.2017.67},
  annote =	{Keywords: Projective geometry, Hilbert geometry, balls}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2017

  • Refine by Author
  • 1 Ahn, Hee-Kap
  • 1 Banerjee, Hridhaan
  • 1 Day, Carmen Isabel
  • 1 Gezalyan, Auguste H.
  • 1 Golovatskaia, Olga
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Computational geometry

  • Refine by Keyword
  • 2 Hilbert metric
  • 2 balls
  • 1 Algorithm
  • 1 Complexity
  • 1 Farthest-point Voronoi diagram
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact