Bichromatic and Equichromatic Lines in ?2 and ?2 |
| |
Authors: | George B Purdy Justin W Smith |
| |
Institution: | 1. Department of Computer Science, University of Cincinnati, Mail Location 30, Clifton Ave, Cincinnati, OH, 45221, USA
|
| |
Abstract: | Let G and R each be a finite set of green and red points, respectively, such that |G|=n, |R|=n−k, G∩R=∅, and the points of G∪R are not all collinear. Let t be the total number of lines determined by G∪R. The number of equichromatic lines (a subset of bichromatic) is at least (t+2n+3−k(k+1))/4. A slightly weaker lower bound exists for bichromatic lines determined by points in ℂ2. For sufficiently large point sets, a proof of a conjecture by Kleitman and Pinchasi is provided. A lower bound of (2t+14n−k(3k+7))/14 is demonstrated for bichromatic lines passing through at most six points. Lower bounds are also established for equichromatic
lines passing through at most four, five, or six points. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|