On point sets with many unit distances in few directions

Peter Braß
Graduiertenkolleg Algorithmische Diskrete Mathematik
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany
email: brass@inf.fu-berlin.de

Report B 97-04
June 1997

We study the problem of the maximum number of unit distances among n points in the plane under the additional restriction that we count only those unit distances that occur in a fixed set of k directions, taking the maximum over all sets of n points and all sets of k directions. We prove that for fixed k and sufficiently large n (depending on k) the extremal sets are essentially sections of lattices, bounded by edges parallel to the k directions and of equal length.

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-97-04.ps.gz