MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

Your problem was addressed in this paper:

Teofilo Gonzalez. "Covering a set of points in multidimensional space." Information Pocessing Letters. 40.4 (1991): 181-188. (Journal link)

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.

Google Scholar finds that Gonzalez's paper was subsequently cited by 80 papers.

I believe his Fig.1 below addresses a form of your question about a finite set of choices:


share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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