Avoiding Distances

Given a finite planar point set $X=\{x_1,\dots ,x_n\}$, let $a_1<a_2<\cdots <a_s$ denote the $s\le \left(\genfrac{}{}{0px}{}{n}{2}\right)$ different (Euclidean) distances between points in $X$. The aim is to retain as many of the points as possible such that certain imposed inter-pair distances are avoided. For example, we show that: (A) Given a set $X$ of $n$ points in the plane, an independent set of size $0.2293n$ in the unit distance graph determined by $X$ can be found in $O(n^2)$ time. For any fixed $k\in \mathbf{N}$ there exists a constant $c_k>0$ such that for any set $X$ of $n$ points in the plane, and set $D$ of size $k$, there exists a subset $X^{\mathrm{\prime }}\subseteq X$ of size $\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }\ge c_k\mathrm{\mid }X\mathrm{\mid }$ in which no pair of points is at some distance in $D$ (we say that $X^{\mathrm{\prime }}$ avoids distances in $D$). Such a set can be found efficiently. (B) (i) There is a subset of $X$ of size $n\mathrm{/}2$ that avoids the maximum distance; this bound cannot be improved. (ii) There is a subset of $X$ of size $8n\mathrm{/}47$ that avoids both the minimum and maximum distance; on the other hand, there exists $X$ such that at most $5n\mathrm{/}16$ points can be retained with this property. (iii) There is a subset of $X$ of size $n\mathrm{/}7$ whose diameter is at most half the original diameter; on the other hand, there exists $X$ such that at most $n\mathrm{/}6$ points can be retained with this property. © (i) For any $\epsilon >0$, a $(1-\epsilon )$-approximation for $\text{textsc}MIS$ in the minimum distance graph of $n$ points in the plane can be found in $2^{O(1\mathrm{/}\epsilon )}{n}^{O(1)}$ time. (ii) Given a set $X$ of $n$ points in the plane, a maximum independent set in the graph of diameters can be computed in $O(n^2)$ time. The techniques used to handle the planar case can be extended to ${\mathbf{R}}^d$ for any fixed dimension $d$.