# Unit covering of $d$-dimensional points

Given a set of points in $X$ axis, we want to cover them with minimum number of unit intervals. For this problem we can assume that each interval in the optimal solution is starting or ending in one of the points.

How can we extend this assumption to the higher dimensions? For example given a set of points in $d$ dimensions and we want to cover them with $d$-dimensional unit disks, can we specify the disks in optimal solution to the finite size (constant to $n$ and maybe polynomial or exponential to $d$) set?

-

He develops algorithms for minimal coverings by cubes, by axis-aligned boxes, and by balls. All three problems are NP-hard for dimensions $d \ge 2$, so only approximation algorithms are available. For $n$ points covered by $s$ cubes (hypersquares), his approximation algorithm takes $O(d n + n \log s)$ time. You will have to look at the paper for the complex time complexities and guaranteed approximation ratios for the various problems.