## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

No Title

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