On the Average Taxicab Distance Function and Its Applications

Generalized conics are subsets in the space all of whose points have the same average distance from a given set of points (focal set). The function measuring the average distance is called the average distance function (or the generalized conic function). In general it is a convex function satisfying a kind of growth condition as the preliminary results of Sect. 2 show. Therefore any sublevel set is convex and compact. We can also conclude that such a function has a global minimizer.

The paper is devoted to the special case of the average taxicab distance function given by integration of the taxicab distance on a compact subset of positive Lebesgue measure in the Euclidean coordinate space.

The first application of the average taxicab distance function is related to its minimizer. It is uniquely determined under some natural conditions such as, for example, the connectedness of the integration domain. Geometrically, the minimizer bisects the measure of the integration domain in the sense that each coordinate hyperplane passing through the minimizer cuts the domain into two parts of equal measure. The convexity and the Lipschitzian gradient property allow us to use the gradient descent algorithm that is formulated in terms of a stochastic algorithm (Sect. 3) to find the bisecting point of a set in \(\mathbb{R}^{n}\).

Example 1 in Sect. 4 shows the special form of the average taxicab distance function of a convex polygon. The level curves (generalized conics) admit semidefinite representations as algebraic curves in the plane because the average taxicab distance function is piecewise polynomial of degree at most three.

Some applications in geometric tomography are summarized as our main motivation to investigate the concept of the average taxicab distance function. Its second order partial derivatives give the coordinate \(X\)-rays of the integration domain almost everywhere and vice versa: the average taxicab distance function can be expressed in terms of the coordinate \(X\)-rays. Therefore the reconstruction of the sets given by their coordinate \(X\)-rays can be based on the average taxicab distance function instead of the direct comparison of the \(X\)-rays. In general (especially, in some classes of non-convex sets), the convergence property of the average taxicab distance function with respect to the Hausdorff convergence of the integration domain is better than the convergence of the \(X\)-rays (see regular and \(X\)-regular convergences in Sect. 4.1) and we can apply a standard approximation paradigm (Footnote 1) to solve the problem.

In the last section we prove that any compact convex body is uniquely determined by the diagonalization of its covariogram function measuring the average taxicab distance of the points from the intersection of the body with the translates of its axis parallel bounding box.