Tangent pairs of (pseudo-)circles

Suppose we have a collection of simple closed curves in the plane. These curves are called pseudo-circles if 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 a weak arrangement of curves.) Circles are, of course, a special case of pseudo-circles. Given a set of n pseudo-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^5/3), which is derived by showing that a certain bipartite graph associated with the curves, with one edge per tangent pair, has no K_3,3 subgraph. An Omega(n^4/3) lower bound follows from an easy modification of a construction by Erdõs of a family of n points and n lines with Omega(n^4/3) incident 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.

If the curves are true circles, the upper bound can be improved to roughly O(n^3/2) by reducing the problem to counting incidences between points and cones in 3-space. The Omega(n^4/3) lower 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.

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 bounds Omega(n^4/3) and O(n^5/3) follow from basically the same arguments as for pseudo-circle tangencies. (The O(n^3/2) upper 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?

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