# Computational Geometry Column 32

## Abstract

The proof of Dey’s new $`k`$-set bound is illustrated.

A $`k`$-set of a set of $`n`$ points $`P`$ in the plane is a set of exactly $`k`$ points of $`P`$ contained in an open halfplane. The maximum number of $`k`$-sets as a function of $`n`$ and $`k>0`$ is an important quantity, but a gap in the known bounds between $`\mathrm{\Omega }(n\mathrm{log}k)`$ and $`O(nk^{1/2})`$ stood for over $`25`$ years. The only progress was a tight bound of $`nk`$ on the number of $`k`$-sets, and a slight lowering of the upper bound for $`k`$-sets to $`O(nk^{1/2}/\mathrm{log}^{}k)`$.<sup>1</sup><sup>1</sup>1 The first result, which will play a role below, is due to Alon and Győri \[AG86\]; the second is due to Pach et al. \[PSS92\]. See \[Ede87\] and \[AAS97\] for history and further references. But recently, building on the work of Agarwal, Aronov, and Sharir \[AAS97\], Tamal Dey improved the upper bound to $`O(nk^{1/3})`$ \[Dey97\]. Here I will sketch his proof<sup>2</sup><sup>2</sup>2 I will follow his first proof, which employs duality. He has since developed a proof that never leaves the primal setting.  on an example.

Consider the set of $`n=10`$ points shown in Fig. 1.<sup>3</sup><sup>3</sup>3 I will assume throughout that no three points of $`P`$ lie on a line, and no two points lie on a vertical. Neither assumption affects the worst-case bounds. The line shown determines a $`5`$-set, as there are exactly $`5`$ points in the halfplane below. In this instance, there are also $`5`$ points above, so this line determines two $`5`$-sets. We will only count the $`k`$-sets below their halfplane bounding line, which clearly suffices for an asymptotic bound; this will be our first reduction.

The next step is familiar to those working in combinatorial geometry: dualize each point of $`P`$ to a line, transforming the point set to an arrangement of lines $`𝒜`$. I will use the transformation $`(a,b)y=axb`$ from primal to dual (and $`(a^{},b^{})y=a^{}xb^{}`$ from dual to primal), which preserves the above-below relation: a point of $`P`$ is below a line $`L`$ iff the dual line is below the point dual to $`L`$. Define the $`k`$-level of $`𝒜`$ to be the closure of the set of points of the lines of $`𝒜`$ that have exactly $`k`$ lines below them. The number of vertices on the $`k`$-level and the number of $`k`$-sets (with $`k`$ points below) differ by at most $`1`$. Take any $`k`$-set line, translate it upward until it hits a point of $`P`$, and then rotate it counterclockwise about that point until it hits another. This line corresponds to a vertex of the $`k`$-level. Fig. 2 shows the $`5`$-level of the arrangement dual to the points in Fig. 1. Note that not every point of the $`5`$-level has five lines below: for example, the rightmost vertex of the level, at $`f=(5,8)`$, has four lines below.<sup>4</sup><sup>4</sup>4 This is why the level was defined via closure, to fill in these holes. Let $`V_k`$ be the set of vertices of $`𝒜`$ with exactly $`k`$ lines below. Then the vertices of the $`k`$-level are precisely $`V_kV_{k1}`$. Thus the vertex at $`f`$ is a member of $`V_4`$; all six vertices in $`V_4`$ are marked with open circles in the figure.

The second reduction is that it suffices to bound $`|V_{k1}|`$, as these vertices correspond to lines through two points of $`P`$ that have exactly $`k1`$ points below them. Perturbing the line corresponding to a vertex of $`V_{k1}`$ results in two $`k`$-sets below. Thus the point $`f=(5,8)`$ in Fig. 2 maps to the line $`y=5x8`$ through points $`(1,18)`$ and $`(2,2)`$ of $`P`$; the perturbation that includes the former point but excludes the latter is the line shown in Fig. 1.

Now Dey defines a straight-line geometric graph $`G`$ in the primal setting that connects a pair of points of $`P`$ with an edge iff the line containing that edge dualizes to a vertex in $`V_{k1}`$. See Fig. 3. We now seek to bound the number of edges $`t=|V_{k1}|`$ of $`G`$. Dey obtained his bound by relating $`t`$ to the number of crossings $`X`$ of edges of $`G`$. In particular, Ajtai et al. \[ACNS82\] and Leighton \[Lei84\] proved that there must be at least $`ct^3/n^2`$ crossings among $`t>4n`$ edges of a straight-line geometric graph, $`c`$ a constant. As the case $`t4n`$ is easy,<sup>5</sup><sup>5</sup>5 Our running example only has $`t=6<4n=40`$. this establishes that $`ct^3/n^2<X`$.

An upper bound for $`X`$ is obtained by a close analysis of the lines below the $`k`$-level, which I will only sketch. Agarwal et al. emphasized in \[AAS97\] a way of viewing those lines that is a key part of Dey’s argument. They partitioned the portion of $`𝒜`$ below the $`k`$-level into a union of $`k`$ concave chains $`c_1,c_2,\mathrm{}`$, which turn only at the vertices of $`V_{k1}`$. Fig. 4 will serve in place of a formal definition. A consequence of our duality is that a pair of crossing edges in $`G`$ corresponds to a line tangent to two concave chains, passing through a vertex of each; see Fig. 5. This bounds $`X`$ by the number of such common tangents. The number of these tangents is in turn bounded from above by the number of times the chains cross each other, as explained in the caption to Fig. 5. As all of these crossings occur below the $`k`$-level of $`𝒜`$, there cannot be more than the number of vertices below this level which, as mentioned previously, is known to be at most $`nk`$.

So we now have $`ct^3/n^2<X<nk`$. Solving for $`t`$ yields $`t=O(nk^{1/3})`$.

Acknowledgements. I thank Pankaj Agarwal, Boris Aronov, Tamal Dey, and Micha Sharir for comments.

(Written 27 July 1997)