Suppose we have a collection of simple closed curves in the plane. These curves are calledpseudo-circlesif every pair either intersects transversely at exactly two points, intersects tangentially at exactly one point, or does not intersect at all. (Grünbaum calls such a collection aweak arrangement of curves.) Circles are, of course, a special case of pseudo-circles.Given a set ofnpseudo-circles, no three of which meet at any point, how many tangent pairs can there be?As far as I know, the best known upper bound is

O(n, which is derived by showing that a certain bipartite graph associated with the curves, with one edge per tangent pair, has no^{5/3})Ksubgraph. An_{3,3}Omega(nlower bound follows from an easy modification of a construction by Erdõs of a family of^{4/3})npoints andnlines withOmega(nincident point/line pairs. (This disproves a conjecture of Grünbaum.) I suspect this lower bound is closer to the truth, at least for convex pseudo-circles.^{4/3})If the curves are true circles, the upper bound can be improved to roughly

O(nby reducing the problem to counting incidences between points and cones in 3-space. The^{3/2})Omega(nlower bound also applies to circles, but only if circles of infinite radius (otherwise known as lines) are allowed. If lines are disallowed, the best lower bound I know of is only slightly superlinear; it follows from another construction of Erdõs of a set of points with many unit distances.^{4/3})Now suppose the (pseudo-)circles are in general position, so that there are no tangent pairs.

How many digons (cells with exactly two vertices) can their arrangement have?The best known boundsOmega(nand^{4/3})O(nfollow from basically the same arguments as for pseudo-circle tangencies. (The^{5/3})O(nupper bound for circle tangencies does not seem to generalize to digons.) In fact, for pseudo-circles, the worst-case bounds for tangencies and digons are provably equal. Is the same true of true circles?^{3/2})For some related open problems, see Hisao Tamaki and Takeshi Tokuyama, "How to Cut Pseudo-Parabolas into Segments", Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 230-237, 1995.

Open Problems - Jeff Erickson (jeffe@cs.duke.edu) 16 Oct 97