On the independence number of minimum distance graphs

Let F=F(n) denote the largest number such that any set of n points in the plane with minimum distance 1 has at least F elements, no two of which are at unit distance. Improving a result by Pollack, we show that F(n)≥ (9/35)n . We also give an O(n log n) time algorithm for selecting at least (9/35)n elements in a set of n points with minimum distance 1 so that no two selected points are at distance 1. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p179.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received June 12, 1996, and in revised form April 22, 1997.