Combinatorics of distances

On this page I list publications that study structures and algorithms that arise from minimising distances to or between points in the plane: Voronoi_diagrams, search_algorithms, and spanners.

A Voronoi diagram of a set of sites S is a subdivision of the plane into regions, one region VR(s) for each element s of S, such that for each point in VR(s), s is the unique closest element of S. Here's a simple example, where S is a set of points (imagine them to be post offices), and the plane is subdivided into regions such that all points in the same region have the same nearest post office:

There are many algorithms to compute a Voronoi diagram and its dual graph, the Delaunay triangulation. I implemented a couple of them in C++ to compare them for speed and, especially, for ease of implementation; you may check out my code here.

But what happens if S is not simply a set of points, or if the distance between a site and a point is not simply the standard Euclidean distance? To support my explorations (and to produce illustrations for our book and articles) I made a simple tool, called Vorosketch, that is relatively inefficient but relatively easy to adapt to different distance measures; feel free to download and use it.

One of our findings is the following. Suppose S is still a simple set of points, the distance between two points s and q in the plane is measured by the L_p distance L_p(s−q), where L_p( (x,y) ) = (|x|^p+|y|^p)^{1/ p}. What happens if p gets close to zero? Surprisingly, although for p close to zero, L_p and L_−p have very different values, they induce almost the same Voronoi diagram. In fact, as p approaches zero from above or from below, the Voronoi diagram converges to the Voronoi diagram of the distance function L_*( (x,y) ) = |xy|. Therefore we propose to define the geometric L₀ distance by L₀( (x,y) ) = |xy|.

• The limit of L_p Voronoi diagrams as p→0 is the bounding-box-area Voronoi diagram.
  By Herman Haverkort and Rolf Klein.
  Computing Research Repository (arXiv.org), 2207.07377, 2022.
  text; GeoGebra worksheet

Thus, we have the following special cases of the (geometric) L_p distance:

L_−∞( (x, y) ) = min( |x|, |y| )
L₀( (x, y) ) = product( |x|, |y| ) (geometric L₀ distance, not to be confused with other distances called L0)
L₁( (x, y) ) = sum( |x|, |y| ) (Manhattan metric)
L₂( (x, y) ) = √( |x|² + |y|² ) (Euclidean metric)
L_∞( (x, y) ) = max( |x|, |y| )

Another type of Voronoi diagram has sites that are points with a direction (for example, a camera, or a football player). The distance from a point s with direction φ to a point p is now defined as the difference between φ and the direction from s to p. In other words: by how much would s have to change its direction (turn around) to be directed at (look at) p? A point p is now in the Voronoi region of s if s is the site that can be directed at p most easily. If all sites can only turn clockwise, then the Voronoi regions will be bounded by circular arcs and straight line segments. If all sites can turn clockwise as well as counterclockwise (whatever requires the smallest turn), then we found that the Voronoi regions are bounded by circular arcs, straight line segments and hyperbolic curves:

• Hyperbolae are the locus of constant angle difference.
  By Herman Haverkort and Rolf Klein.
  Computing Research Repository (arXiv.org), 2112.00454, 2021.
  text

Suppose we want to locate a target on a line, or in higher-dimensional space. To this end we can issue point queries. The response to each query tells us where the query point fits in between the previously issued query points if we would order them by increasing distance to the target (or, for example, by decreasing strength of a signal received from the target). How should we choose our query points to locate the target with the highest precision, if a) all query points must be issued at once; b) we may issue a fixed number of query points one by one, choosing each next point in reaction to the response so far; c) we may issue query points one by one, but we do not know in advance how many queries we get to issue?

• How to play hot and cold.
  By Herman Haverkort, David Kübel, Elmar Langetepe, and Barbara Schwarzwald.
  Computational Geometry, 87:101596, 2020.
  text

The dilation of a network with respect to a pair of points p, q in the plane is the distance from p to q in the network divided by the distance from p to q as the crow flies. Suppose we want to connect a set of points P in the plane by a network with total edge length at most L, such that we minimise the maximum dilation over all pairs of points from P. When L is just big enough to be able to construct the minimum Steiner tree of P (the smallest network that connects all points of P), then that is the solution, and when L is big enough to construct a direct connection between each pair of points P, then that is the solution. But what kind of structures do we create for values of L in between these extremes? The following paper provides a partial answer for the case that P consists of three points:

• Restricted-Weight Minimum-Dilation Spanners on Three Points.
  By Kevin Buchin, Herman Haverkort, and Hidde Koerts.
  Canadian Conference on Computational Geometry (CCCG 2020), pages 240-248, 2021.
  text