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