Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Incidence problems for points and unit circles
Andras Bezdek, Auburn University
We will study mainly the structure of incidences between a finite
point configuration and a set of unit circles.
The following is a
well-known problem of Sylvester: Show that for a finite set of
at least two
non-collinear points in a plane there exists a line through exactly two
of the points. Sylvester's problem was first verified by Gallai, and
it inspired further research considering generalizations and other
problems of similar type. In particular,
P. Elliot studied the analogue of this problem for circles, by estimating the
number of circles passing through exactly 3 points.
We initiate a sequence of
problems by asking if among the unit circles connecting pairs of points there
exist one which contains exactly two points.
A circle is ordinary if it contains exactly two points of
a given point set. An arrangement of four points is E4arrangement (where E stands for exceptional) if three of the points
are vertices of an acute triangle with circumradius 1, and the fourth point
is the common point of that other three circles which go through two vertices
of this triangle. Notice that each unit circle which goes through two points
of an E4 pointset contains exactly three of them. We say that four circles
form an e4 arrangement (where e stands again for exceptional),
if their intersection points form an E4 point set.
Notice that each point which belongs to two circles of an e4 arrangement
belongs to exactly three of them.
We conjecture that
for any finite set of at least two points in the
plane which is different from E4 and has diameter at most 2,
there is a unit circle passing through exactly two points of the set.
We also believe that any finite set of unit circles which is different
from e4 and has connected union determines an intersection point
belonging to exactly two of those circles.
In a joint paper with F. Fodor and I. Talata we proved the first conjecture
under the assumption that the diameter of the point set is at most 
.
Later the author proved the same if the diameter is at most 
.
As far as we can tell none of the classical incidence problems for points and lines has been
considered for points and unit circles before. If this is the case a number of elegant open questions can be
considered. For example one could strengthen one of the authors early
results
on the minimum number of intersection points determined by a finite number of unit circles.
Back
