On \(k\)-sets in arrangements of curves and surfaces (Q1179129)

The article considers simple curves in two dimensions each of which separates the plane into two connected components, the interior and the exterior of the curve. Given a set \(S\) of such curves, the \(k\)-set of \(S\) is defined as the set of those intersection points which are covered by \(k\) interiors. The \(\leq k\)-set is defined analogously. Various bounds on the size of \(\leq k\)-sets are given, for example \({\mathcal O}(nk)\) if any two curves intersect at most twice, \(\Theta(nk\alpha(n/k))\) (\(\alpha\) is the inverse of the Ackermann-function) if they intersect at most three times, and \(\Theta(k^ 2\lambda_ s(n/k))\) if they are \(x\)-monotone and intersect at most \(s\) times. These results are obtained by applying a probabilistic technique of Clarkson and Shor to relate the size of \((\leq k)\)-sets to the size of 0-sets of a sample of the curves. Several applications of these results are given including efficient data structures for disc-stabbing, i.e. reporting from a set of discs in the plane all those that contain a given query point, with generalizations to half-planes (bounded by curves) and arbitrary disjoint convex sets.