DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.27

The Squishy Grid Problem

Authors: Zixi Cai, Kuowen Chen, Shengquan Du, Arnold Filtser, Seth Pettie, and Daniel Skora

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

In this paper we consider the problem of approximating Euclidean distances by the infinite integer grid graph. Although the topology of the graph is fixed, we have control over the edge-weight assignment w : E → ℝ_{≥ 0}, and hope to have grid distances be asymptotically isometric to Euclidean distances, that is: For all grid points u,v, dist_w(u,v) = (1± o(1))‖u-v‖₂. We give three methods for solving this problem, each attractive in its own way. - Our first construction is based on an embedding of the recursive, non-periodic pinwheel tiling of Radin and Conway [Charles Radin, 1994; Radin and Sadun, 1996; John H. Conway and Charles Radin, 1998] into the integer grid. Distances in the pinwheel graph are asymptotically isometric to Euclidean distances, but no explicit bound on the rate of convergence was known. We prove that the multiplicative distortion of the pinwheel graph is (1 + 1/Θ(log^ξ log D)), where D is the Euclidean distance and ξ = Θ(1). The pinwheel tiling approach is conceptually simple, but can be improved quantitatively. - Our second construction is based on a hierarchical arrangement of highways. It is simple, achieving stretch (1 + 1/Θ(D^{1/9})), which converges doubly exponentially faster than the pinwheel tiling approach. - The first two methods are deterministic, with rigorous guarantees. An even simpler approach is to sample the edge weights independently and randomly from a common distribution D. Whether there exists a distribution D^* that makes grid distances Euclidean, asymptotically and in expectation, is major open problem in the theory of first passage percolation. Previous experiments show that when D is a Fisher distribution (which is continuous), grid distances are within 1% of Euclidean distances. We demonstrate experimentally that this level of accuracy can be achieved by a simple 2-point distribution that assigns weights 0.41 or 4.75 with probability 44% and 56%, respectively.

Cite as

Zixi Cai, Kuowen Chen, Shengquan Du, Arnold Filtser, Seth Pettie, and Daniel Skora. The Squishy Grid Problem. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.SoCG.2026.27,
  author =	{Cai, Zixi and Chen, Kuowen and Du, Shengquan and Filtser, Arnold and Pettie, Seth and Skora, Daniel},
  title =	{{The Squishy Grid Problem}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.27},
  URN =		{urn:nbn:de:0030-drops-258333},
  doi =		{10.4230/LIPIcs.SoCG.2026.27},
  annote =	{Keywords: grid graph, Euclidean distance, metric embedding, first passage percolation}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2024.25

Delaunay Triangulations in the Hilbert Metric

Authors: Auguste H. Gezalyan, Soo H. Kim, Carlos Lopez, Daniel Skora, Zofia Stefankovic, and David M. Mount

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

The Hilbert metric is a distance function defined for points lying within the interior of a convex body. It arises in the analysis and processing of convex bodies, machine learning, and quantum information theory. In this paper, we show how to adapt the Euclidean Delaunay triangulation to the Hilbert geometry defined by a convex polygon in the plane. We analyze the geometric properties of the Hilbert Delaunay triangulation, which has some notable differences with respect to the Euclidean case, including the fact that the triangulation does not necessarily cover the convex hull of the point set. We also introduce the notion of a Hilbert ball at infinity, which is a Hilbert metric ball centered on the boundary of the convex polygon. We present a simple randomized incremental algorithm that computes the Hilbert Delaunay triangulation for a set of n points in the Hilbert geometry defined by a convex m-gon. The algorithm runs in O(n (log n + log³ m)) expected time. In addition we introduce the notion of the Hilbert hull of a set of points, which we define to be the region covered by their Hilbert Delaunay triangulation. We present an algorithm for computing the Hilbert hull in time O(n h log² m), where h is the number of points on the hull’s boundary.

Cite as

Auguste H. Gezalyan, Soo H. Kim, Carlos Lopez, Daniel Skora, Zofia Stefankovic, and David M. Mount. Delaunay Triangulations in the Hilbert Metric. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gezalyan_et_al:LIPIcs.SWAT.2024.25,
  author =	{Gezalyan, Auguste H. and Kim, Soo H. and Lopez, Carlos and Skora, Daniel and Stefankovic, Zofia and Mount, David M.},
  title =	{{Delaunay Triangulations in the Hilbert Metric}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.25},
  URN =		{urn:nbn:de:0030-drops-200657},
  doi =		{10.4230/LIPIcs.SWAT.2024.25},
  annote =	{Keywords: Delaunay Triangulations, Hilbert metric, convexity, randomized algorithms}
}

Search Results

Documents authored by Skora, Daniel

The Squishy Grid Problem

Abstract

Cite as

Delaunay Triangulations in the Hilbert Metric

Abstract

Cite as

Thanks for your feedback!

Could not send message