7
$\begingroup$

For a 2D closed convex shape, with metric $d$ and fixed area $A$, we can calculate the average distance between random (interior) points. For different shapes, we will get different values for this average. We can ask, for which shape is this average a minimum (in terms of $A$). For the Euclidean metric, the answer is the circle. If we pick a different metric, what shape do we get?

$\endgroup$
  • $\begingroup$ A few comments about your question, concerning possibly implicit assumptions. First, when you say 2D you mean that the underlying set is $\mathbb{R}^2$? Or some other notion of dimension? Are you going to assume that the metric is translation invariant? or more general? Do you have a specific metric in mind? What is the measure you are going to use for defining "average distance"? $\endgroup$ – Willie Wong Feb 27 at 14:34
  • $\begingroup$ Yes, $\mathbb{R}^2$. General metric (not necessarily translation invariant). No specific metric in mind. The measure for distance is the metric. $\endgroup$ – Michael Mc Gettrick Feb 27 at 15:00
  • $\begingroup$ How do you define area? Just the usual one for R2? $\endgroup$ – enthdegree Feb 27 at 15:14
  • $\begingroup$ @MichaelMcGettrick: not the measure for distance. The measure for defining averages. (You are presumably integrating over an area and dividing by the total area for taking averages, what is the area measure?) $\endgroup$ – Willie Wong Feb 27 at 15:23
  • $\begingroup$ Ah, okay, I guess I have not thought about the metric for the area A, or for the averaging: But then one can still pose this question for discrete case, area corresponding to N points, divide by N for average (as replied by Joseph below). $\endgroup$ – Michael Mc Gettrick Feb 27 at 15:48
12
$\begingroup$

Here is an answer for lattice points and using the $L_1$ (Manhattan) metric:

Demaine, Erik D., Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, and Mariano Zelke. "Integer point sets minimizing average pairwise $L_1$ distance: What is the optimal shape of a town?." Computational Geometry 44, no. 2 (2011): 82-94. PDF download.


  Fig4


The continuous version of the same problem is addressed in this paper:

Bender, Carl M., Michael A. Bender, Erik D. Demaine, and Sándor P. Fekete. "What is the optimal shape of a city?." Journal of Physics A: Mathematical and General 37, no. 1 (2003): 147. Journal link.

From the Abstract: "In this paper a nonlinear differential equation for the boundary curve of such a city is determined."


          City


$\endgroup$
3
$\begingroup$

For an arbitrary metric and measure, this is going to be a very difficult question to answer. The shape of the minimizer will depend on the choice of metric and measure, if it exists at all. Joseph O'Rourke discussed the $L^1$ distance already, so I'm going to focus on distance functions which are either symmetric, or else induced by a smooth Riemannian metric. These sorts of questions are known as extremal problems [1] and are closely related to isoperimetric inequalities, which are an active area of research.

As noted in the comments, we need to specify which measure we use to compute averages. It appears that there are at least two natural choices of measure.

  1. the Lebesgue measure on $\mathbb{R}^2$
  2. the measure induced by a Riemannian metric

As I mentioned earlier, the particular shape of the minimizer will depend on the choice of distance function and measure. However, from a variational standpoint, there is a fairly general principle which is very helpful.

A convex region $S$ is a critical point for the average distance between interior points iff the integral $\int_S d(p,x) \, d \mu(x)$ is constant for all $p \in \partial S$. Here, $\mu$ is the measure used to determine averages.

In other words, a region $S$ is a possible minimizer for the average distance between points if the average distance between a point $p$ on the boundary of $S$ and interior points in $S$ does not depend on $p$. It's possible to prove this rigorously using variational techniques or using Crofton's differential equation (for a good exposition, see [2]). However, the basic intuition is that if this property does not hold, we can slightly change the shape of $S$ so as to reduce the total average distance.

From this, there are a few immediate consequences.

  1. If the distance function is translation and rotationally symmetric and the measure we use is the Lebesgue measure on $\mathbb{R}^2$, the disk is a critical point. Oftentimes, this will be the unique critical point (and thus also the minimum), but any proof of this seems likely to depend on the particular details of the distance function.

  2. If we consider a surface of constant curvature with its natural distance function and induced measure, the critical points for the average distance between points are geodesic balls. There is no guarantee that geodesic balls will be convex in the choice of coordinates you use, but they will be the minimizers nonetheless.

For more general (non-symmetric) Riemannian metrics (with their induced distance function and measure), this question is much more difficult, and the variational principles are less useful. However, with a lower bound on the sectional curvature, it is possible to get a lower bound on the areas of geodesic balls. Using this, it should be possible to establish uniform lower bound on the average distance between points in a region of area $A$. However, these sorts of estimates don't tell you what the minimizer looks like (or even if it exists at all). It is possible to construct distance functions where no minimizer exists, by incorporating patches where the curvature is more and more negative.

[1] Bauer, Christina; Schneider, Rolf, Extremal problems for geometric probabilities involving convex bodies, Adv. Appl. Probab. 27, No. 1, 20-34 (1995). ZBL0827.52004.

[2] Eisenberg, Bennett; Sullivan, Rosemary, Crofton’s differential equation, Am. Math. Mon. 107, No. 2, 129-139 (2000). ZBL0986.60011.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.