On the independence number of minimum distance graphs |
| |
Authors: | G Csizmadia |
| |
Institution: | (1) Courant Institute, New York University, New York, NY 10012, USA, US |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|