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 *E*_{4}*arrangement* (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 *E*_{4} pointset contains exactly three of them. We say that four circles
form an *e*_{4}* arrangement* (where *e* stands again for *exceptional*),
if their intersection points form an *E*_{4} point set.
Notice that each point which belongs to two circles of an *e*_{4} 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 *E*_{4} 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 *e*_{4} 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