---

Source. The Remark, p. 187, of G. Csizmadia, On the Independence Number of Minimum Distance Graphs, Discrete Comput. Geom. 20 (1998), 179--187, DOI 10.1007/PL00009381; see the source card. The abstract (p. 179) states the same result.

Statement

Remark (p. 187). For a set of $n$ points in the plane with minimum distance $1$, the proof of the Theorem gives an algorithm that selects at least $\frac{9}{35}n$ of the points with no two selected points at distance $1$, and it runs in $O(n\log n)$ time.

Proof pointer

The paper's justification (p. 187): the minimum distance graph can be built in $O(n\log n)$ time; each step of the algorithm finds between $1$ and $9$ new independent points, as in Lemma 1, in at most a constant number of operations, a large constant the paper does not specify; and there are at most $n$ steps. The paper gives no further detail of how a step is carried out.

Dependencies

Lemma 1 and the Theorem of the same paper. Read depth: claims checked; the remark was read on the print, and its complexity argument is the paper's brief sketch, not checked further.

Bears on

• Problem 1066: an algorithmic form of the bound $g(n)\ge\frac{9}{35}n$; it adds nothing to the bound itself.