% Time-stamp: <2012-08-31 23:23:57 Boris Aronov> \documentclass[11pt]{article} %% Useful mostly in PDFLaTeX mode, but still nice. \usepackage{microtype} \usepackage{latexsym,graphicx,amsmath,amssymb,amsthm} \usepackage[dvipsnames,usenames]{color} \usepackage{fullpage,cite,enumerate} \def\marrow{\marginpar[\hfill$\longrightarrow$]{$\longleftarrow$}} \def\micha#1{\textcolor{Purple}{(Micha says: }\marrow\textsf{#1})} \let\Micha\micha \def\rom#1{\textcolor{green}{(Rom says: }\marrow\textsf{#1})} \let\Rom\rom \newcommand{\boris}[2][says]{\textcolor{MidnightBlue}{Boris #1: }\marrow\textsf{#2}} \let\Boris\boris \def\muriel#1{\textcolor{CarnationPink}{(Muriel says: }\marrow\textsf{#1})} \let\Muriel\muriel % \def\emo#1{\textcolor{RubineRed}{(Emo says: }\marrow\textsf{#1})} % \let\Emo\emo %\newtheorem{theorem}{Theorem}[section] \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{fact}[theorem]{Fact} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem*{remark}{Remark} \def\D{\mathcal{D}} \def\L{\mathcal{L}} \def\mdangle{{\measuredangle}} \let\bd\partial \let\eps\varepsilon \DeclareMathOperator{\CH}{CH} \begin{document} \title{On the Union Complexity of Diametral Disks\thanks{% Work on this paper by Boris Aronov, Muriel Dulieu, and Micha Sharir has been supported by Grant 2006/194 from the U.S.-Israel Binational Science Foundation. Work on this paper by Boris Aronov has also been supported by NSA MSP Grant H98230-10-1-0210. Work on this paper by Boris Aronov and Muriel Dulieu has also been supported by NSF Grants CCF~08-30691 and CCF~11-17336. Work on this paper by Rom Pinchasi has been supported by ISF grant (grant No. 1357/12) and by BSF grant (grant No. 2008290) from the U.S.-Israel Binational Science Foundation. Work by Micha Sharir has also been supported by NSF Grant CCF-08-30272, by Grant 338/09 from the Israel Science Fund, by the Israeli Centers of Research Excellence (I-CORE) program (Center No.~4/11), and by the Hermann Minkowski--MINERVA Center for Geometry at Tel Aviv University. Most of work on this paper was done at the Centre Interfacultaire Bernoulli, EPFL, Lausanne, Switzerland, in September 2010, and was partially supported by the Swiss National Science Foundation. A preliminary version of this work was presented at the \emph{2011 Fall Workshop on Computational Geometry}.}} \author{ Boris Aronov\thanks{% Department of Computer Science and Engineering, Polytechnic Institute of NYU, Brooklyn, NY~11201-3840, USA; \texttt{aronov@poly.edu}.% } \and Muriel Dulieu\thanks{% Department of Computer Science and Engineering, Polytechnic Institute of NYU, Brooklyn, NY~11201-3840, USA; \texttt{mdulieu@gmail.com}.% } \and Rom Pinchasi\thanks{% Faculty of Mathematics, The Technion, Haifa 32000, Israel; \texttt{room@math.technion.ac.il}.% } \and Micha Sharir\thanks{% School of Computer Science, Tel Aviv University, Tel Aviv 69978 Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA; \texttt{michas@post.tau.ac.il}.% } % \and Emo Welzl\thanks{% % Institut f\"ur Theoretische Informatik, ETH Z\"urich, CH-8092 % Z\"urich, Switzerland; {\tt emo@inf.ethz.ch}. } } % \date{} \maketitle \begin{abstract} Let $S$ be a set of $n$ points in the plane, and let $\D$ be an arbitrary set of disks, each having a pair of points of $S$ as a diameter. We show that the combinatorial complexity of the union of elements in $\D$ is $O(n^{3/2})$, and provide a lower bound construction with $\Omega(n^{4/3})$ complexity. If the points of $S$ are in convex position, the upper bound drops to $O(n\log n)$. \end{abstract} \paragraph{The problem.} Let $S$ be a set of $n$ points in the plane, and let $E$ be a collection of unordered pairs of points of $S$. For each pair $\{a,b\}\in E$ let $D_{ab}$ denote the disk with diameter $ab$; we refer to $D_{ab}$ as the \emph{diametral disk} determined by $\{a,b\}$. Let $\D$ denote the resulting collection of disks, and let $U$ denote their union. Let the \emph{complexity} of~$U$ be measured by the number of its \emph{vertices}, namely intersection points of two disk boundaries that lie on the boundary $\bd U$ of $U$. In this paper we establish the following upper and lower bounds on the complexity of~$U$. %, which we measure by the number of vertices, namely, %intersection points of two disk boundaries, on its boundary $\bd U$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem} \label{main} The maximum possible complexity of the union of any number of diametral disks determined by any set of pairs of points from an $n$-point set in the plane is $\Omega(n^{4/3})$ and $O(n^{3/2})$. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% If the points of $S$ are in convex position, the upper bound on the union complexity improves considerably: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem} \label{conv} The complexity of the union of any number of diametral disks determined by any set of pairs of points from an $n$-point set in convex position in the plane is $O(n\log n)$. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \paragraph{Preliminary properties.} As is well known, the complexity of $U$, being the union of $|E|$ disks, is $O(|E|)$ \cite{KLPS}, so the problem becomes more challenging as $|E|$ grows. We call a disk $D_{ab}\in\D$ \emph{essential} if it appears on the boundary of the union $U$ at some point which does not belong to any other disk; that is, it contributes a nonempty arc, or several arcs, to $\bd U$. We eliminate all non-essential disks, noting that every vertex of $U$ is also a vertex of the union of the essential disks. (Notice that this latter union can have more features on its boundary, because the removal of the non-essential disks might expose new vertices which now lie on the union boundary.) On the other hand, as each essential disk contributes to the boundary, their number provides a natural lower bound, and, in view of the bound in \cite{KLPS}, (up to a constant multiplicative factor) also an upper bound, on the union complexity. In other words, it suffices to establish the upper bounds in Theorems~\ref{main} and~\ref{conv} on the number of essential disks in $\D$ and this holds trivially also for the lower bound in Theorem~\ref{main}. \begin{lemma}\label{fact:1} Fix a point $a\in S$ and consider the set $E_a$ of all the neighbors of $a$ in $E$. Let $U_a$ denote the union of the disks $D_{ab}$, for $b\in E_a$, and let $C_a$ denote the convex hull of $E_a\cup\{a\}$. Then (i)~$C_a\subset U_a$ and (ii)~the disks $D_{ab}$ that appear on $\bd U_a$ (in the above sense, of contributing at least one nonempty arc to $\bd U_a$) are precisely those for which $b$ is a vertex of~$C_a$. \end{lemma} \begin{proof} Let $D_{ab}$ and $D_{ac}$ be two disks in $\D$ with the common diametral endpoint $a$. The boundaries of these disks meet at $a$ and at another point $q$ which has to lie on the line passing through $b$ and $c$; $q$ can lie either between $b$ and $c$ (as in Figure~\ref{2ddisks}(a)) or past $b$ or $c$ (as in Figure~\ref{2ddisks}(b)). In either case the entire triangle $abc$ is covered by the union $D_{ab}\cup D_{ac}$. \begin{figure}[htb] \centering \input{2ddisks.pstex_t} \caption{Two diametral disks with a common diametral endpoint.} \label{2ddisks} \end{figure} To prove (i), we note that $C_a$ is the union of all triangles $ab_1b_2$, for $b_1, b_2\in E_a$ (in fact, it suffices to take only those triangles for which $b_1$, $b_2$ are consecutive hull vertices), and the preceding argument implies that each of these triangles is contained in $U_a$. To prove~(ii), consider a point $b\in E_a$ which is not a vertex of $C_a$. There exist two points $b_1,b_2\in E_a$ that are consecutive vertices of $C_a$ such that $b$ lies in the triangle $ab_1b_2$; see Figure~\ref{onlyhull}. \begin{figure}[htb] \centering \input{onlyhull.pstex_t} \caption{Illustrating the proof that only hull neighbors of $a$ can generate essential disks with $a$.} \label{onlyhull} \end{figure} Let $b'$ be the intersection point of the line $ab$ with the line $b_1b_2$ ($b'=b$ when $b$ lies on the segment $b_1b_2$). Note that $D_{ab}$ is fully contained in $D_{ab'}$, which is fully contained in $D_{ab_1} \cup D_{ab_2}$. For the latter property, note that $\bd D_{ab'}$ passes through $a$ and through the second intersection point $q$ of $\bd D_{ab_1}$ and $\bd D_{ab_2}$ (because, by construction, $\angle aqb' = \pi/2$). Hence $D_{ab'}$ belongs to the pencil of disks determined by $a$ and $q$. Since the center of $D_{ab'}$ lies between those of $D_{ab_1}$ and $D_{ab_2}$, it is contained in the union of these two disks. Note that $\bd D_{ab'}$ meets $\bd ( D_{ab_1} \cup D_{ab_2} )$ only at $a$ and $q$, and thus does not contribute any \emph{arc} to $\bd U_a$. To see that the converse also holds, consider a vertex $b$ of $C_a$. Draw a supporting line~$\ell$ to $C_a$ through~$b$, so that $\ell\cap C_a = \{b\}$, and mark on it the foot $q$ of the perpendicular to $\ell$ from $a$. Clearly, $q$ belongs to $\bd D_{ab}$, but it cannot belong to any other disk $D_{ab'}$ because, by construction, the angle $\angle aqb'$ is acute. This completes the proof of property~(ii). \end{proof} % \micha{Fix Figure 2 according to the new proof.} In other words, every essential disk in $\{D_{ab} \mid b\in E_a\}$ is such that $b$ is a vertex of $C_a$ (note that not all those disks necessarily contribute to the overall union $U$). We may therefore remove all other disks from $\D$. Hence, in what follows we will assume that the set $E_a$ of all the neighbors in $E$ of any $a\in S$ lie in convex position, and that either $a$ lies in their hull or $E_a\cup\{a\}$ is also in convex position. \paragraph{Proof of the upper bound in Theorem~\ref{main}.} We turn the set $E$ into a \emph{directed} geometric graph~$G$. The vertices of $G$ are the points in $S$. We orient an edge (drawn as a straight line segment) from $a$ to $b$ if $\{a,b\} \in E$, and the semicircle of $\bd D_{ab}$ which lies counterclockwise from $a$ to $b$ appears (at least in part) on $\bd U$; we refer to this semicircle as the \emph{CCW-semicircle} of $D_{ab}$. Since we only deal with essential disks, each pair in $E$ becomes either a single edge or a pair of anti-parallel edges of~$G$. See Figure~\ref{d_graph}. \begin{figure}[htb] \centering \input{d_graph.pstex_t} \caption{The directed graph $G$.} \label{d_graph} \end{figure} Without loss of generality we may assume that a constant portion (in fact an eighth) of the directed edges of $G$ form an angle of at most $\pi/8$ with the $y$-axis and point downwards. We delete all other edges from the graph $G$ and bound the number of the remaining edges. This way we may lose a constant factor of at most eight in the upper bound. Let $G'$ denote the new directed geometric graph. We use the well-known fact that, for any directed graph $\tilde{G}(V,E)$ on $n$~vertices, there exists a partition of $V$ into sets $A$ and $B$ so that at least $|E|/4$ edges of $\tilde{G}$ emanate from vertices of $A$ and terminate at vertices of $B$.\footnote{% To see this, assign independently each vertex $v\in V$ to $A$ or to $B$ with equal probability. An edge $(u,v)\in E$ will have $u\in A$ and $v\in B$ with probability $1/4$, so the expected number of such edges is $|E|/4$, so at least one assignment has at least $|E|/4$ edges directed from $A$ to $B$.} Applying this partitioning to $G'$, we obtain a new directed bipartite geometric graph $H$, without losing more than a factor of four in the number of edges; overall, we have $|E(G)| \le 32 |E(H)|$. Let a \emph{directed} $K_{2,2}$ be (a graph isomorphic to) the directed graph on four vertices $a,b,u,v$ with edges $(a,u)$, $(a,v)$, $(b,u)$, $(b,v)$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lemma} \label{no22x} $H$ does not contain a copy of a directed $K_{2,2}$ as a subgraph. \end{lemma} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{proof} Suppose to the contrary that $H$ does contain such a subgraph. That is, there exist four points $a,b,u,v$ in $S$ so that all ordered pairs in $\{a,b\}\times\{u,v\}$ are in $H$. Suppose first that $a,b,u,v$ are in convex position. Since all edges of $H$ point downwards, $a$ and $b$ are both higher than $u$ and $v$, so $ab$ and $uv$ are edges of the hull. Hence, the edges of $H$ consist of the two other hull edges and the two diagonals of the hull. That is, in this case $au, av, bu, bv$ form a self-intersecting quadrangle (see Figure \ref{diskno22x}). Otherwise, $a,b,u,v$ are not in convex position. In this case, as is easily verified, $au$, $av$, $bu$, and $bv$ form a non-convex simple quadrangle (see Figure \ref{non_conv_k22}). We consider separately these two cases. We start with the more difficult case in which $au$, $av$, $bu$, and $bv$ form a self-intersecting quadrangle, where some pair of edges, say $av$ and $bu$, cross. This implies that, up to relabeling, the situation is as depicted in Figure~\ref{diskno22x}. That is, $a$, $b$, $v$, and $u$ are in convex position, appearing in this clockwise order along the boundary of their convex hull $Q$, and the CCW-semicircles of all four disks $D_{au}$, $D_{av}$, $D_{bu}$, and $D_{bv}$ appear on the boundary of~$U$. For any pair of points $p,q$ we denote by $\ell_{pq}$ the directed line passing through $p$ and $q$ and oriented from $p$ to $q$. In the hypothetical configuration, the right halfplane of $\ell_{bv}$, that is, the halfplane delimited by $\ell_{bv}$ and lying on its right side, contains $a$, $u$, and the CCW-semicircle of $D_{bv}$; see Figure~\ref{diskno22x}. % \begin{figure}[htb] \centering \input{diskno22x.pstex_t} \caption{Illustrating the impossibility of a self-intersecting copy of a directed $K_{2,2}$ in~$H$.} \label{diskno22x} \end{figure} % By assumption, there exists a point $q$ on this semicircle which appears on the boundary of the union of all the disks and thus also on that of the four disks $D_{au}$, $D_{av}$, $D_{bu}$, and $D_{bv}$. The preceding arguments imply that $q$ cannot lie inside the convex hull $Q$. If $q$ lies to the left of the line $\ell_{uv}$ (in the halfplane containing $Q$; consider the point $q$ in Figure~\ref{diskno22x}---in the figure $q$ also lies to the left of $\ell_{ab}$, but the proof does not exploit this property), then we must have $\angle uqb = \angle uqv + \angle vqb > \angle vqb = \frac{\pi}{2}$, implying that $q$ lies inside the disk $D_{bu}$, contrary to our assumption. A symmetric argument applies when $q$ lies to the right of $\ell_{ab}$ (consider the point~$q'$ in Figure~\ref{diskno22x}). It therefore remains to consider the case where $q$ lies on the opposite sides of both lines, which can happen only when these lines meet at a point $w$ to the right of $\ell_{bv}$, and when $q$ lies in the wedge $W$ formed at $w$ by the intersection of these two opposite halfplanes. Refer to $q''$ in Figure~\ref{diskno22x}; to conform with the notation in the figure, we refer to this point as $q''$ in the remainder of the argument. We claim that in this case the CCW-semicircle of $D_{au}$ cannot appear on the union boundary. Indeed, suppose to the contrary that there exists a point $p$ in that semicircle that lies on the union boundary. By assumption, $p$ has to lie to the right of $\ell_{au}$, and outside the triangle $q''bv$. Hence, $p$ cannot lie both to the right of $\ell_{ab}$ and to the left of $\ell_{uv}$. If $p$ lies to the left of $\ell_{ab}$, then $\angle upb > \angle upa=\frac{\pi}{2}$, so $p$ lies inside $D_{bu}$, a contradiction. The symmetric case where $p$ lies to the right of $\ell_{uv}$ is handled similarly. These contradictions imply that $au$, $av$, $bu$, and $bv$ cannot form a self-intersecting quadrangle. \medskip Next we analyze the remaining case in which $au$, $av$, $bu$, and $bv$ form a non-convex simple quadrangle. \begin{figure}[htb] \centering \input{non_conv_k22.pstex_t} \caption{The case where $au$, $av$, $bu$, and $bv$ form a non-convex simple quadrilateral.} \label{non_conv_k22} \end{figure} There are two cases to consider here. \medskip \noindent \textbf{Case 1.} One of $\{a,b\}$, say $b$, is not a vertex of the convex hull of $\{a,b,u,v\}$. We assume the situation is as depicted in Figure \ref{non_conv_k22}(a). We claim that no point of the CCW-semicircle of $D_{bu}$ can appear on the boundary of $U$, contradicting the fact that $bu$ is a directed edge in $G$. To see this, let $p$ be any point on the CCW-semicircle of $D_{bu}$. By definition of $H$, we have $\angle aub \leq \pi/4$ and $\angle uab <\angle uav \leq \pi/4$. It thus follows that $\angle uba =\pi-\angle aub-\angle uab > \pi/2$. Since $\angle uab \le \pi/4$ it follows that $a$ lies outside $D_{bu}$. Now if $p$ and $b$ lie on opposite sides of $au$ then $\angle upa > \angle upb = \pi/2$ and then $p$ lies inside $D_{au}$. If $p$ and $b$ lie on the same side of $au$ then $\angle upa>\angle uba \ge \pi/2$, again implying that $p$ lies inside $D_{au}$. In either case $p$ cannot appear on $\bd U$, as claimed, and the resulting contradiction shows that Case 1 is impossible. \medskip \noindent \textbf{Case 2.} One of $\{u,v\}$, say $v$, is not a vertex of the convex hull of $\{a,b,u,v\}$. We assume the situation is as depicted in Figure \ref{non_conv_k22}(b). We claim that no point of the CCW-semicircle of $D_{av}$ can appear on the boundary of $U$, contradicting the fact that $av$ is a directed edge in $G$. To see this, let $p$ be any point on the CCW-semicircle of $D_{av}$. By definition of $H$, we have $\angle uav \leq \pi/4$ and $\angle auv <\angle aub \leq \pi/4$. It thus follows that $\angle uva =\pi-\angle uav-\angle auv > \pi/2$. Since $\angle auv \le \pi/4$ it follows that $u$ lies outside $D_{av}$. Now if $p$ and $v$ lie on opposite sides of $au$ then $\angle upa > \angle vpa = \pi/2$ and then $p$ lies inside $D_{au}$. If $p$ and $v$ lie on the same side of $au$ then $\angle upa>\angle uva \ge \pi/2$, again implying that $p$ lies inside $D_{au}$. In either case $p$ cannot appear on $\bd U$, as claimed, and the resulting contradiction shows that Case 2 is impossible too. \end{proof} We conclude that the (directed) graph $H$ does not contain a copy of a (directed)~$K_{2,2}$. This is well known to imply (see the theorem of K\H ovari-S\'os-Tur\'an \cite{KST}) that $H$ (and therefore~$G$) can have at most $O(n^{3/2})$ edges. It follows that $\D$ contains at most $O(n^{3/2})$ essential disks, and thus its union has complexity $O(n^{3/2})$, completing the proof of the upper bound in Theorem~\ref{main}. \paragraph{Lower bound.} We next show that the complexity of $U$ can be $\Omega(n^{4/3})$ in the worst case. We construct the following set $S$ of $\Theta(n)$ points. One half of the set, $S_1$, consists of the vertices of the $\sqrt{n}\times\sqrt{n}$ integer grid, centered at the origin (for this, assume, without loss of generality, that $\sqrt{n}$ is an odd integer). As shown by Erd{\H o}s and others (see, e.g., \cite{Ed}), there exists a set $L$ of $m=\Theta(n)$ distinct lines, each containing $\Theta(n^{1/3})$ points of $S_1$. By applying an appropriate projective transformation, which only slightly moves the points of $S_{1}$, we may assume that no two lines in $L$ are parallel. We then shrink and rotate the plane, so that $S_1$ is contained in the unit disk around the origin, and so that no line of $L$ is vertical. All these transformations preserve the $\Theta(n^{4/3})$ incidences between the points of $S_1$ and the lines of $L$. We next take a circle $C$ centered at the origin with a sufficiently large radius $r$, and form the set $S_2$ of the intersection points of $C$ with the lines of $L$. Each line in $L$ intersects $C$ at two points, but we put in $S_2$ only the point with positive $x$-coordinate (when $r$ is sufficiently large there will be exactly one such point). \begin{lemma} \label{lem:5r} For all sufficiently large values of $r$ the following condition holds: For any pair $q_1,q_2$ of distinct points of $S_{2}$ and for every point $p$ in the unit disk around the origin, the disk $D_{pq_1}$ does not intersect the disk of radius $5/r$ around $q_2$. \end{lemma} \begin{proof} As no two lines in~$L$ are parallel, for sufficiently large~$r$ the distance between every pair of points in $S_{2}$ can be assumed to be larger than~$10$. We need to lower bound the distance from $q_2$ to the center $c$ of $D_{pq_1}$. Write $p=(2a,2b)$, with $a^2+b^2<\frac14$. Assume, without loss of generality, that $q_1=(r,0)$, and write $q_2=(r\cos\theta, r\sin\theta)$, with $\theta>0$. We then have $c=\left(\frac{r}{2}+a,b\right)$. We need a lower bound for $\|cq_2\|-\|cq_1\|$. For this we write \[ \|cq_2\|-\|cq_1\| = \frac{ \|cq_2\|^2-\|cq_1\|^2 }{ \|cq_2\|+\|cq_1\| } \ge \frac{ \|cq_2\|^2-\|cq_1\|^2 }{4r} . \] Substituting the above expressions for $c$, $q_1$, and $q_2$, we obtain \begin{align*} \|cq_2\|-\|cq_1\| & \ge \frac{1}{4r} \left( (r(\cos\theta - 1/2) - a)^2 + (r\sin\theta - b)^2 - (r/2-a)^2 - b^2 \right) \\ & = \frac{1}{4r} \left(r^2((\cos\theta - 1/2)^2 +\sin^2\theta -1/4) -2r( a(\cos\theta - 1/2) + b\sin\theta - a/2) \right) \\ & = \frac{r}{4} (1-\cos\theta) + \frac12 (a(1-\cos\theta) - b\sin\theta) . \end{align*} Clearly, when $r$ is sufficiently large, the term $\frac12 a(1-\cos\theta)$ is negligible compared with the leading term, so we can write, say, \[ \|cq_2\|-\|cq_1\| \ge \frac{2r\sin^2(\theta/2)}{5} -\frac14\sin\theta . \] We have assumed that $\|q_1q_2\|\ge 10$, so $\sin(\theta/2) = \|q_1q_2\|/(2r) \ge 5/r$. In this case the second term in the above expression is smaller than half the first term, so we have \[ \|cq_2\|-\|cq_1\| \ge \frac{r\sin^2(\theta/2)}{5} \ge \frac{5}{r} , \] completing the proof. \end{proof} We now put $S:= S_1\cup S_2$; we have $|S|=\Theta(n)$. See Figure~\ref{diamlow}. \begin{figure}[htb] \centering \input{diamlow.pstex_t} \caption{The (still unperturbed) lower bound construction.} \label{diamlow} \end{figure} The construction so far is not the end of the story. We next distort $S=S_{1} \cup S_{2}$ by mapping each point $p=(x,y)$ to the point $p^*=(x,y+\eps x^2)$, where $\eps>0$ is a sufficiently small parameter. This turns each line $\ell=\{y=a_{\ell}x+b_{\ell}\} \in L$ into a parabola $\ell^*=\{y=a_{\ell}x+b_{\ell}+\epsilon x^2\}$ which is still incident to $\Theta(n^{1/3})$ points of the perturbed copy $S_1^*$ of $S_1$. The final step in the construction uses the set $S^*=S_{1}^* \cup S_{2}^*$ and defines the following set $\D$ of diametral disks on $S^*$. For each line $\ell\in L$ we add to $\D$ all diametral disks of the form~$D_{p^*q^*}$, where $q^*$ is the point $S_2^*\cap\ell^*$ and where $p^*\in S_1^*\cap\ell^*$. Clearly, $|\D| = \Theta(n^{4/3})$. We claim that all disks in $\D$ are essential, which readily implies the asserted lower bound. To show that all disks in $\D$ are essential, consider a line $\ell\in L$ and its associated parabola $\ell^*$. Let $p^*_1,\ldots,p^*_k$ denote the points of $S_{1}^*$ on $\ell^*$, appearing there in this left-to-right order, and let $q^*$ denote the single point of $S_{2}^*$ on $\ell^*$; see Figure~\ref{dchain}. Since all these points are in convex position, it follows from Lemma~\ref{fact:1} that all the disks $D_{p_i^*q^*}$, for $i=1,\ldots,k$, are essential within their own union~$U_{q^*}$. Moreover, if $\eps$ is sufficiently small, the boundaries of these disks intersect only within the disk~$\tilde{D}_q$ of radius $1/r$ around $q^*$ (when $\eps=0$, all these disks are tangent to each other at $q^*=q$). Hence, each of these disks, except for the largest one, can appear along $\bd U_{q^*}$ (and therefore also along $\bd U$) only within $\tilde{D}_q$. By Lemma~\ref{lem:5r}, these appearances are disjoint from all the disks constructed on the other points of $S_2^*$, and therefore the corresponding disks are all essential in $U$. This establishes the lower bound, and thereby completes the proof of Theorem~\ref{main}. $\Box$ % \micha{Enlarge Fig. 6, or at least enlarge the text (compare with % other figs.} % \boris{As per Micha's instructions, I enlarged text in Fig. 6. Looks % a bit ugly, though.} \begin{figure}[htb] \centering \input{dchain.pstex_t} \caption{The convex chain $p_1^*,\ldots,p_k^*,q^*$ lies on a common parabola.} \label{dchain} \end{figure} \paragraph{Proof of Theorem~\ref{conv}.} Consider next the case where the points of $S$ are in convex position, and denote by $\CH(S)$ their convex hull. As in the general case, we are also given a set $E$ of unordered pairs of points of $S$, and a corresponding set $\D$ of diametral disks $D_{ab}$, for $\{a,b\}\in E$. As before, we let $U$ denote the union of these disks. Again, we construct a directed geometric graph $G$ on $S$ so that, for each essential disk $D_{au}\in\D$ whose CCW-semicircle from $a$ to $u$ appears on $\bd U$, we add the directed edge $(a,u)$ to $G$. \begin{figure}[htb] \centering \input{acuobt.pstex_t} \caption{Left: $(a,u)$ is an acute chord. Right: $(a,u)$ is an obtuse chord.} \label{acuobt} \end{figure} We distinguish between three types of edges $(a,u)$ of $G$; we refer to them collectively as \emph{chords} (of $\CH(S)$): \begin{description} \item{\textbf{(i) An acute chord:}} Every pair of lines $\ell_a$, $\ell_u$ that support $\CH(S)$ at $a$ and $u$, respectively, either do not meet at all in the right halfplane of $\ell_{au}$, or meet there at an acute angle (the angle at which the intersection point of $\ell_{a}$ and $\ell_{u}$ sees the segment $au$). See Figure~\ref{acuobt}(left). \item{\textbf{(ii) An obtuse chord:}} Every pair of supporting lines $\ell_a$, $\ell_u$, as above, meet in the right halfplane of $\ell_{au}$ at an obtuse angle (at which their intersection point sees $au$). See Figure~\ref{acuobt}(right). \item{\textbf{(iii) A right-angle chord:}} There exist a pair of supporting lines $\ell_a$, $\ell_u$, as above, that meet in the right halfplane of $\ell_{au}$ at a right angle. As is easily verified, a chord which is neither acute nor obtuse must be a right-angle chord. \end{description} The number of right-angle chords is $O(n)$, as easily follows by an argument based on rotating calipers~\cite{T83}. (As we rotate a right-angle wedge so that it contains $\CH(S)$ and touches it at two points, the right-angle chords are exactly those which connect the appropriately directed pairs of contact points, and these pairs change only $O(n)$ times.) To obtain an upper bound on the number of acute and obtuse chords we employ an argument similar to that used by F\"uredi~\cite{Fu}, which involves forbidden submatrices in a $0/1$ matrix. We recall the following result of Furedi: \begin{lemma}[F\"uredi~\cite{Fu}] \label{lem:F} Let $A$ be an $n\times n$ $0/1$ matrix which does not contain the $2\times 3$ submatrix \[ A_0 = \begin{pmatrix} 1 & 1 & \ast \\ 1 & \ast & 1 \end{pmatrix}, \] where $\ast$ denotes any value. That is, there do not exist a pair of rows $i j$. Hence, $A^{(1)}$ is upper triangular matrix, and the nonzero entries of the matrix $A^{(2)}$ lie above the reflected main diagonal. The condition imposed on $G$ is easily seen to imply the nonexistence of $A_0$ in $A^{(1)}$, and symmetric considerations imply that $A^{(2)}$ also does not contain $A_{0}$ as a submatrix. By Lemma~\ref{lem:F}, each of $A^{(1)}$ and $A^{(2)}$ has $O(n\log n)$ $1$s. Since these matrices record all edges of $G$, the corollary follows. \end{proof} We are now ready to bound the number of acute chords. We consider the subgraph $G_a$ of $G$ consisting only of the acute chords, and claim that $G_a$ does not contain as a subgraph the directed graph in the statement of Corollary~\ref{cor:F}. That is, there do not exist five vertices $a_1,a_2,u_3,u_2,u_1$ of $\CH(S)$ in this counterclockwise order along $\bd \CH(S)$, so that $(a_1,u_1)$, $(a_2,u_1)$, $(a_1,u_2)$, and $(a_2,u_3)$ are all directed edges in $G_a$. See Figure~\ref{furedidi}(left) for an illustration of this forbidden subgraph. \begin{figure}[htb] \centering \input{furedidi.pstex_t} \caption{Left: An impossible realization of $A_0$ in the acute case. Right: The obtuse case.} \label{furedidi} \end{figure} To prove the claim, assume to the contrary that $G_a$ does contain such a subgraph. Consider the lines $\ell_{a_1a_2}$ and $\ell_{u_1u_2}$, and assume that they meet at a point $w$ that lies to the right of $\ell_{a_1u_1}$; the analysis is much simpler if they do not meet in the right halfplane of $\ell_{a_1u_1}$ and we handle this case separately below. Arguing as in the proof of the upper bound in Theorem~\ref{main}, the existence of the three chords $(a_1,u_1)$, $(a_1,u_2)$, and $(a_2,u_1)$ in $G_a$ implies that any point $q$ on the CCW-semicircle of $D_{a_1u_1}$ which appears on the union boundary must lie in the wedge $W$ which is the intersection of the right halfplane of $\ell_{a_{1}a_{2}}$ and the left halfplane of $\ell_{u_{1}u_{2}}$ (and therefore has $w$ as an apex; see Figure~\ref{furedidi}(left)). We claim that the angle at which $w$ sees $a_1u_1$ is acute. This in turn will imply that $q$ must also see $a_1u_1$ at an acute angle and thus cannot lie on $\bd D_{a_1u_1}$, contrary to assumption. To prove that the angle at which $w$ sees $a_{1}u_{1}$ is acute we make use of the existence of the fourth acute chord~$(a_2,u_3)$. Take any supporting line $\ell_{a_2}$ to $\CH(S)$ at $a_2$ and any supporting line $\ell_{u_3}$ to $\CH(S)$ at $u_3$. Because $a_{1},a_{2},u_{3},u_{2},$ and $u_{1}$ are in convex position in this counterclockwise order on $\CH(S)$, it follows that $\ell_{a_{2}}$ and $\ell_{u_{3}}$ must meet at a point $z$ that lies in the wedge opposite to $W$. By definition, $z$ sees the segment $a_2u_{3}$ at an acute angle. This implies that $z$ sees the segment $a_{1}u_{1}$ at an acute angle, which in turn implies that $w$ sees the segment $a_{1}u_{1}$ at an acute angle, thereby reaching the desired contradiction. To complete the analysis, notice that if $\ell_{a_1a_2}$ and $\ell_{u_1u_2}$ do not meet in the right halfplane of $\ell_{a_1u_1}$, then the wedge $W$ does not exist, leaving no place for the point $q$, and thereby leading to an immediate contradiction. Since $G_a$ does not contain the forbidden subgraph of Corollary~\ref{cor:F}, we conclude that it has at most $O(n\log n)$ edges. We next consider the case of obtuse chords, and handle it using a ``mirror image'' of the preceding argument. Specifically, we now consider the directed subgraph $G_o$ of $G$ which consists only of the obtuse chords, and claim that $G_o$ does not contain as a subgraph the ``reflection'' of the subgraph in the statement of Corollary~\ref{cor:F}. That is, there do not exist five vertices $a_1,a_2,u_3,u_2,u_1$ of $\CH(S)$ in this \emph{clockwise} order along $\bd \CH(S)$, so that $(a_1,u_1)$, $(a_2,u_1)$, $(a_1,u_2)$, and $(a_2,u_3)$ are all directed edges in~$G_o$. See Figure~\ref{furedidi}(right) for an illustration of this forbidden subgraph. Assume to the contrary that $G_o$ does contain a copy of the above subgraph. Consider the lines $\ell_{a_2a_1}$ and $\ell_{u_2u_1}$, and assume that they meet at a point $w$ in the right halfplane of $\ell_{a_1u_1}$ (as the analysis will imply, they must indeed meet in this manner). By arguments similar to those in the proof of the upper bound in Theorem~\ref{main}, the existence of the three chords $(a_1,u_1)$, $(a_1,u_2)$, and $(a_2,u_1)$ in $G_o$ implies that any point $q$ on the CCW-semicircle of $D_{a_1u_1}$ which appears on the union boundary must lie in the triangle bounded by $\ell_{a_1a_2}$, $\ell_{u_1u_2}$, and $\ell_{a_1u_1}$. We claim that the angle at which $w$ sees the segment $a_1u_1$ is obtuse, which in turn will imply that $q$ must also see $a_1u_1$ at an obtuse angle and thus cannot lie on $\bd D_{a_1u_1}$, contrary to assumption. To prove that the angle at which $w$ sees $a_{1}u_{1}$ is obtuse we make use of the existence of the fourth obtuse chord $(a_2,u_3)$. Take any supporting line $\ell_{a_2}$ to $\CH(S)$ at $a_2$ and any supporting line $\ell_{u_3}$ to $\CH(S)$ at $u_3$. By definition, $\ell_{a_{2}}$ and $\ell_{u_{3}}$ meet at a point $z$, and $\angle a_{2}zu_{3}$ is obtuse. Since the points $a_{2},a_{1},u_{1},u_{2},$ and $u_{3}$ lie in convex position in that counterclockwise order on the boundary of $\CH(S)$, it follows that $w$ lies in the triangle bounded by $\ell_{a_{2}}, \ell_{u_{3}},$ and $a_{2}u_{3}$. We have $\angle a_{1}wu_{1} > \angle a_{1}wu_{3} = \angle a_2wu_3 > \angle a_{2}zu_{3}$. Hence $\angle a_{1}wu_{1}$ is obtuse, thereby reaching the desired contradiction. (Note that, as mentioned above, the analysis does indeed imply that $\ell_{a_1a_2}$ and $\ell_{u_1u_2}$ meet to the right of $\ell_{a_1u_1}$.) Again, since $G_o$ does not contain the (reflection of the) forbidden subgraph of Corollary~\ref{cor:F}, we conclude that it has at most $O(n\log n)$ edges. Hence $G$ has $O(n\log n)$ edges, and this implies the asserted bound on the number of essential disks in $\D$, and thus also on the complexity of the union~$U$. This completes the proof of Theorem~\ref{conv}.\hspace{1ex plus 1fill}$\Box$ \begin{remark} Note that the proof, in both acute and obtuse cases, actually holds if we replace the chord $(a_2,u_3)$ by a chord $(a_3,u_3)$, where $a_3$ is any point lying between $a_2$ and $u_3$. That is, we also exclude the existence of the submatrix $\left( \begin{smallmatrix} 1 & 1 & \ast \\ 1 & \ast & \ast \\ \ast & \ast & 1 \end{smallmatrix} \right)$ in both $A^{(1)}$ and $A^{(2)}$. Unfortunately, this in itself does not imply a better upper bound, as already noted by Pettie~\cite{Pex}, citing previously known constructions. \end{remark} \paragraph{Discussion.} The main contribution of this paper is to show that the maximum possible complexity of the union of any collection of diametral disks defined over a set of $n$ points in the plane, is neither quadratic nor linear. Still there is a significant gap between our lower and upper bounds, and the main obvious open problem is to close this gap. When the given points are in convex position, the upper bound drops to $O(n\log n)$, but we do not know whether the bound is worst-case tight. Therefore, here too there is a gap to close. A linear lower bound on the number of essential disks is trivial. Is there a superlinear construction? If, instead of requiring the disks in $\D$ to be diametral, we only insist that every disk in $\D$ pass through a (distinct) pair of points of $S$, the number of essential disks might be quadratic in the worst case. To see this, take $S$ to be a set of $n$ points in general position in a unit disk, and let $\gamma$ be a concentric circle with generic radius larger than~$2$. For each pair $a,b$ of distinct points in $S$, draw a disk $D_{ab}$ which passes through $a$ and $b$ and is tangent to $\gamma$ (from the inside). The general position of $S$ and a generic choice of the radius of $\gamma$ ensure that all the points of tangency between these disks and $\gamma$, which clearly lie on the boundary of the union of the disks, are all distinct, so all the disks are essential. Hence, some restriction must be imposed on the disks of $\D$ to obtain subquadratic behavior. Does the union complexity remain subquadratic when (a) in each disk $D_{ab}$ the chord $ab$ has the same central angle, or when (b) these central angles are bounded away from $0$ (by an angle independent of $n$) or sufficiently close to $\pi$? More ambitiously, does our upper bound continue to hold when one replaces disks by homothetic copies of some fixed convex shape $K$? Here one might define, for a given pair of points $a,b$, the corresponding diametral copy $K_{ab}$ of $K$ to be the smallest homothetic copy of $K$ that contains both $a$ and $b$. What is the complexity of the union of any subset of diametral copies of $K$ determined by pairs of points from a set of $n$ points in the plane? \medskip The motivation for studying the problem of the union of diametral disks came from a recent study of a subset of the authors~\cite{ADH09} on witness Gabriel graphs. Specifically, a \emph{(negative) witness Gabriel graph} for a pair of point sets $P,Q$ in the plane is the geometric graph with vertex set~$P$, where $p,p' \in P$ are connected by an edge if the diametral disk $D_{pp'}$ contains no points of $Q$. We were considering the problem of testing whether a given geometric graph $G$, on a given vertex set $P$ and a given witness set $Q$, is indeed a witness Gabriel graph. For this one needs to verify that the union of the diametral disks corresponding to the edges of $G$ does not contain any point of $Q$. A natural question that then arises is to obtain bounds on the complexity of such a union, which is what we have done in this paper. We note that applying the (upper) bounds that we have derived in the context of witness Gabriel graphs requires some care. Two issues arise: (a) The size of $G$ may be large, so unless it is encoded in some compact form, the bound on the union complexity may not lead to a comparably efficient algorithm. (b) One also needs to tackle the complementary problem, of verifying that each disk corresponding to a non-edge of $G$ contains a point of~$Q$. % We have not considered seriously the problem of constructing a lower % bound for Theorem~\ref{conv}. Arranging for $\lfloor n/2 \rfloor$ % completely disjoint disks is easy, but % % As for the upper bound in Theorem~\ref{conv}, the argument presented % implies the absence of the following patterns: \(\left( % \begin{smallmatrix} % 1 & 1 & \ast \\ % 1 & \ast & 1 % \end{smallmatrix} % \right)\), \(\left( % \begin{smallmatrix} % 1 & 1 \\ % 1 & \ast \\ % \ast & 1 % \end{smallmatrix} % \right)\), and \(\left( % \begin{smallmatrix} % 1 & 1 & \ast \\ % 1 & \ast & \ast \\ % \ast & \ast & 1 % \end{smallmatrix} % \right).\) Can a better bound be proven for matrices that exclude all % three patterns? There is extensive existing literature on forbidden % patterns in 0/1~matrices which perhaps may help find an answer to this % question; see, for example, % \cite{BG,Pettie-JCT-11,Pettie-SoCG-11}. \Boris{that's just a sample.} \begin{thebibliography}{99} \bibitem{ADH09} B. Aronov, M. Dulieu, and F. Hurtado, Witness {G}abriel graphs, \emph{Comput. Geome. Theory Appls.}, in print, see also \\ %% Do not see how to make it look nice --BA \texttt{http://dx.doi.org/10.1016/j.comgeo.2011.06.004}. %\bibitem{BG} D. Bienstock and E. Gy\"ori, An extremal problem on %sparse 0-1 matrices, \emph{SIAM J.~Discrete Math.} 4 (1991), 17--27. \bibitem{Ed} H. Edelsbrunner, \emph{Algorithms in Combinatorial Geometry}, Springer-Verlag, Heidelberg, 1987. \bibitem{Fu} Z. F\"uredi, The maximum number of unit distances in a convex $n$-gon, \emph{J. Combinat. Theory, Ser.~A} 55 (1990), 316--320. \bibitem{KLPS} K. Kedem, R. Livn\'e, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. \emph{Discrete Comput. Geom.} 1(1)~(1986), 59--71. \bibitem{KST} T. K\H ovari, V. T. S\'os, and P. Tur\'an, On a problem of K. Zarankiewicz, \emph{Colloquium Mathematicum} 3 (1954), 50--57. %\bibitem{MT} A. Marcus and G. Tardos, Intersection reverse sequences % and geometric applications, \emph{J. Combinat. Theory Ser.~A} 113 % (2006), 675--691. %\bibitem{Pettie-JCT-11} %S. Pettie, %Generalized Davenport-Schinzel sequences and their 0-1 matrix %counterparts, %\emph{J. Combin. Theory, Series A} 118 (2011), 1863--1895. %\bibitem{Pettie-SoCG-11} S. Pettie, On the structure and composition of %forbidden sequences, with geometric applications, in %\emph{Proc. 27th Annu. ACM Symp. Comput. Geometry}, pp.~370--379, %2011. \bibitem{Pex} S. Pettie, Degrees of non-linearity in forbidden 0--1 problems, \emph{Discrete Math.} 311 (2011), 2396--2410. %\bibitem{PR} R. Pinchasi and R. Radoi\v{c}i\'c, Topological graphs % with no self-intersecting cycle of length $4$, in \emph{Towards a % Theory of Geometric Graphs} (J. Pach, ed.), Contemporary % 5 Mathematics 342, AMS, Providence, RI, 2004, 233--243. \bibitem{T83} G.T. Toussaint, Solving geometric problems with the rotating calipers, \emph{Proc. IEEE MELECON'83}, Athens, Greece, (1983), pp.~A10.02/1--4. \end{thebibliography} \end{document}