On the taxicab distance sum function and its applications in discrete tomography

Abstract

Let a finite set $F\subset \mathbb {R}^n$ be given. The taxicab distance sum function is defined as the sum of the taxicab distances from the elements (focuses) of the so-called focal set F. The sublevel sets of the taxicab distance sum function are called generalized conics because the boundary points have the same average taxicab distance from the focuses. In case of a classical conic (ellipse) the focal set contains exactly two different points and the distance taken to be averaged is the Euclidean one. The sublevel sets of the taxicab distance sum function can be considered as its generalizations. We prove some geometric (convexity), algebraic (semidefinite representation) and extremal (the problem of the minimizer) properties of the generalized conics and the taxicab distance sum function. We characterize its minimizer and we give an upper and lower bound for the extremal value. A continuity property of the mapping sending a finite subset F to the taxicab distance sum function is also formulated. Finally we present some applications in discrete tomography. If the rectangular grid determined by the coordinates of the elements in $F\subset \mathbb {R}^2$ is given then the number of points in F along the directions parallel to the sides of the grid is a kind of tomographic information. We prove that it is uniquely determined by the function measuring the average taxicab distance from the focal set F and vice versa. Using the method of the least average values we present an algorithm to reconstruct F with a given number of points along the directions parallel to the sides of the grid.