International Journal of Computational Geometry & Applications

In this paper, we introduce the notion of $k$-centerpoints for any set $P$ of $n$ points in ${ℝ}^d$. These unify and generalize previous results such as the classical centerpoint theorem,¹ and the recently-proven ray-shooting theorem.² We define two variants: affine $k$-centerpoints, and topological $k$-centerpoints. We prove their equivalence in ${ℝ}^2$, and conjecture that these are in fact equivalent in any dimension. We present the first non-trivial bounds for these problems in ${ℝ}^d$, as well as present several conjectures related to them.

An exact computation of the persistent Betti numbers of a submanifold $X$ of a Euclidean space is possible only in a theoretical setting. In practical situations, only a finite sample of $X$ is available. We show that, under suitable density conditions, it is possible to estimate the multidimensional persistent Betti numbers of $X$ from the ones of a union of balls centered on the sample points; this even yields the exact value in restricted areas of the domain.

Using these inequalities we improve a previous lower bound for the natural pseudodistance to assess dissimilarity between the shapes of two objects from a sampling of them.

Similar inequalities are proved for the multidimensional persistent Betti numbers of the ball union and the one of a combinatorial description of it.

Motivated by Leinster-Cobbold measures of biodiversity, the notion of the spread of a finite metric space is introduced. This is related to Leinster’s magnitude of a metric space. Spread is generalized to infinite metric spaces equipped with a measure and is calculated for spheres and straight lines. For Riemannian manifolds the spread is related to the volume and total scalar curvature. A notion of scale-dependent dimension is introduced and seen for approximations to certain fractals to be numerically close to the Minkowski dimension of the original fractals.

In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set $S$ of $n$ unit disks in ${ℝ}^2$. We first present a simple $O\left(n\log k\right)$ time 5-factor approximation algorithm for this problem, where $k$ is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time $O\left(n^8\log n\right)$ and $O\left(n^{15}\log n\right)$ respectively [M. De, G. K. Das, P. Carmi and S. C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disks, Int. J. of Computational Geometry and Appl., 22(6):461–477, 2013]. We show that the time complexity of the in-place 4-factor approximation algorithm for this problem can be improved to $O\left(n^6\log n\right)$. A minor modification of this algorithm produces a $\frac{14}{3}$-factor approximation algorithm in $O\left(n^5\log n\right)$ time. The same techniques can be applied to have a 3-factor and a $\frac{45}{13}$-factor approximation algorithms in time $O\left(n^{11}\log n\right)$ and $O\left(n^{10}\log n\right)$ respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present $\frac{5}{2}$-factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem.