text:
\section{Introduction}

The \textit{dynamic planar point location} problem is one of the most fundamental and extensively studied problems in geometric data structures, and is defined as follows: We are given a connected planar polygonal subdivision $\Pi$ with $N$ edges. For any given query point $p$, the goal is to find the face of $\Pi$ that contains $p$, subject to insertions and deletions of edges. An equivalent formulation, which we use here is as follows: given a set $S$ of $N$ interior-disjoint line segments in the plane, for any given query point $p$, report the first line segment in $S$ that a vertical upwards-facing ray from $p$ intersects, subject to insertions and deletions of segments.

Dynamic planar point location has many applications in spatial databases, geographic information systems (GIS), computer graphics, etc. Moreover it is a natural generalization of the dynamic dictionary problem with predecessor queries; this problem can be seen as the one dimensional variant of planar point location.

In this paper we focus on the External Memory model, also known as the  Disk Access Model (DAM)~\cite{AggarwalV88}.
The DAM is the standard method of designing algorithms that efficiently execute on large datasets stored in secondary storage.
This model assumes a two-level memory hierarchy, called disk and internal memory and it is parameterized by values $M$ and $B$; the disk is partitioned into blocks of size $B$, of which $M/B$ can be stored in memory at any given moment. The cost of an algorithm in the DAM is the number of block transfers between memory and disk, called Input-Output operations (I/Os). The quintessential DAM-model data structure is the B-Tree \cite{DBLP:journals/acta/BayerM72}.
See~\cite{Vitter01,Vitter06} for surveys.
Many applications of dynamic planar point location, such as GIS problems, must efficiently process datasets that are too massive to fit in internal memory, thus it is of great relevance and interest to consider the problem in the DAM and to devise I/O\ efficient algorithms.

\subsection{Previous Work}

\paragraph{{\normalfont{\textbf{RAM Model.}}}} In the RAM model (the leading model for applications where all data fit in the internal memory) the dynamic planar point location problem has been extensively studied~\cite{ArgeBG06,BaumgartenJM94,ChiangT92,ChengJ92,ChanN15,GoodrichT98}. It is a  major and long-standing open problem in computational geometry to design a data structure that supports queries and updates in $O(\log N)$ time~\cite{Chazelle91,Chazelle94,Snoeyink04}, i.e., to achieve the same bounds as for the dynamic dictionary problem. In a recent breakthrough, Chan and Nekrich in FOCS'15~\cite{ChanN15} presented a data structure supporting queries in $O(\log N (\log \log N)^2)$ time and updates in $O(\log N (\log \log N))$ time. They also showed the tradeoff of supporting queries in $O(\log N)$ time and updates in $O((\log N)^{1+\epsilon})$ time or vice-versa for $\epsilon>0$.

Recently Oh and Ahn~\cite{Gamwtikorea} presented the first data structure for a more general setting where the polygonal subdivision $\Pi$ is not necessarily connected; their data structure supports queries in $O(\log N (\log \log N)^2)$ time and updates in $O(\sqrt{N} \log N (\log \log N)^{3/2} )$ amortized time.
\paragraph{{\normalfont{\textbf{External Memory model}} (See Table~\ref{tab:results}).}}

Several data structures have been presented over the years which support queries and updates in polylog($N$) I/Os \cite{AgarwalABV99,ArgeV04,ArgeBR12}. Table~\ref{tab:results} contains a list of results of prior work. The best update bound known is by Arge, Brodal and Rao~\cite{ArgeBR12} and achieves $O(\log_B N)$ amortized I/Os.  The query time of their data structure is $O(\log^2_B N)$. Very recently, the first data structure that supports queries in $o(\log^2_B N)$ I/Os\ was announced by Munro and Nekrich~\cite{MN19}. In particular they support queries in $O(\log_B N (\log \log_B N)^3)$ I/Os. However their update time is slightly worse than logarithmic, $O(\log_B N (\log \log_B N)^2)$.

\setlength{\tabcolsep}{0.4em}
{\renewcommand{\arraystretch}{1.5

\begin{table}[t]
\begin{center}
\resizebox{\linewidth}{!}{
\begin{tabular}{| c | c | l | l | l |}
\hline
Reference & Space & Query Time & Insertion Time & Deletion Time \\
\hline
Agarwal et al.~\cite{AgarwalABV99} & $O(N)$ & $O(\log^2_{B}{N})$ & $O(\log^2_{B}{N})$ & $O(\log^2_{B}{N})$ \\
Arge and Vahrenhold~\cite{ArgeV04} & $O(N)$ &  $O(\log^2_{B}{N})$ & $O(\log^2_{B}{N})$ & $O(\log_{B}{N})$ \\
Arge et al.~\cite{ArgeBR12} & $O(N)$ &  $O(\log^2_{B}{N})$ & $O(\log_{B}{N})$ & $O(\log_{B}{N})$ \\
Munro and Nekrich~\cite{MN19} & $O(N)$ &  $O(\log_{B}{N}\log^3 \log_B{N})$ & $O(\log_{B}{N}\log^2 \log_B{N})$ & $O(\log_{B}{N}\log^2 \log_B{N})$ \\
\hline
This paper & $O(N)$ & $O(\log^2_{B}{N})$ & $O((\log_{B}{N})/B^{1-\epsilon})$ & $O((\log_{B}{N})/B^{1-\epsilon})$ \\
\hline
\end{tabular}
}
\end{center}
\caption{Overview of results on dynamic planar point location in external memory. Query bounds are worst-case and update bounds are amortized. Space usage is measured in words.
}
\label{tab:results}
\end{table}
}

\paragraph{{\normalfont{\textbf{Fast Updates in External Memory.}}}} One of the most intriguing and practically relevant features of the external memory model is that it allows fast updates. For the dynamic dictionary problem with predecessor queries, the optimal update bound in the RAM model is $O(\log N)$. In external memory, however, $B$-trees achieve the optimal query time of $O(\log_B N)$ and typical update time of $O(\log_BN)$, although substantially faster update times are possible. Brodal and Fagerberg~\cite{BrodalF03} showed that $O(\frac{1}{B^{1-\epsilon}}\log_B N)$ amortized I/Os\ per update can be supported, for small positive constant, $\epsilon$, while retaining $O(\log_B N)$-time queries; they further showed that this is an asymptotically optimal tradeoff between updates and queries. Observe that this update bound is a huge speedup from $O(\log_B N)$ and that for reasonable choices of parameters, e.g.~$B\geq 1000$, $N<10^{93}$, $\epsilon=\frac{1}{2}$, this yields a subconstant amortized number of I/Os\ per update.

Given this progress and the fact that in the RAM model the bounds achieved for planar point location and the dictionary problem are believed to coincide, it is natural to conjecture that a similar update bound can be achieved for the dynamic planar point location problem. However, to date no result has been presented that achieves sublogarithmic insertion or deletion time.

\subsection{Our Results}

We consider the dynamic planar point location problem in the external memory model and present the first data structure with sublogarithmic amortized update time of $O(\frac{1}{B^{1-\epsilon}}\log_B N)$ I/Os. Prior to our work, the best update bound for both insertions and deletions was $O(\log_B N)$, achieved by Arge et al.~\cite{ArgeBR12}.
Our main result is:

\begin{theorem}[Main result]
\label{thm:main}
For a constant $0 < \epsilon \leq 1/2$, there exists a data structure which uses $O(N)$ space, answers planar point location queries in $O((1/\epsilon)^2 \cdot \log^2_B N) = O(\log^2_B N) $ I/Os\ and supports insertions and deletions in $O(\log_B N/(\epsilon \cdot B^{1-\epsilon})) = O((\log_B N)/B^{1-\epsilon})$ amortized I/Os. The data structure can be constructed in $O((N/B) \log_B N)$ I/Os.
\end{theorem}

To obtain this result, several techniques are used.
Our primary data structure is
an augmented \textit{interval tree}~\cite{DBLP:journals/ipl/EdelsbrunnerM81}.
We combine both the primary interval tree and two  auxiliary structures described below with the \textit{buffering} technique~\cite{BrodalF03,Arge03} to improve insertion and deletion bounds.
In Section~\ref{sec:overview} we prove Theorem~\ref{thm:main} using our auxiliary structures as black boxes and omit some technical details relating to rebuilding; these details are deferred to Section~\ref{sec:restucture}.

Our first auxiliary structure answers vertical ray-shooting queries among non-intersecting segments whose left (right) endpoints lie on the same vertical line. This is called the \textit{left (right) structure}.
Left/Right structures of Agarwal et al.~\cite{AgarwalABV99}, which support queries and updates in $O(\log_B{K})$ I/Os, are used by several prior works~\cite{AgarwalABV99,ArgeV04,ArgeBR12}. Our structure improves on their result by reducing the update bound by a factor of $B^{1-\epsilon}$. We obtain the following result, the proof of which is the topic of Section~\ref{sec:left_right}:

\begin{theorem}[Left/right structure]
\label{lem:left_right}
For a set of $K$ non-intersecting segments whose right (left) endpoints lie in the same vertical line and a constant $0 < \epsilon \leq 1/2$, we can create a data structure which supports vertical ray-shooting queries in $ O((1/\epsilon) \cdot \log_B K) = O(\log_B K)$ I/Os\ and insertions and deletions in $O((\log_B K)/( \epsilon \cdot B^{1-\epsilon}))=O((\log_B K)/B^{1-\epsilon})$ amortized I/Os. This data structure uses $O(K)$ space and it can be constructed in $O((K/B) \log_B K)$ I/Os. If the segments are already sorted, it can be constructed in $O(K/B)$ I/Os.
\end{theorem}

Our second auxiliary structure answers vertical ray-shooting queries among non-intersecting segments whose endpoints lie in a set of $\ensuremath{B^{\epsilon /2}}+1$ vertical lines. These vertical lines define $\ensuremath{B^{\epsilon /2}}$ vertical slabs, hence the structure is called a \textit{multislab} structure.  We obtain the following result, the proof of which is the topic of Section~\ref{sec:multislab}:

\begin{theorem}[Multislab structure]
\label{lem:multislab}
For a constant $0 < \epsilon \leq 1/2$ and set of $K$ non-intersecting segments whose endpoints lie in $\ensuremath{B^{\epsilon /2}}+1$ vertical lines, we can create a data structure which supports vertical ray-shooting queries in $O( (1/\epsilon) \cdot \log_B K)=O( \log_B K)$ I/Os\ and insertions and deletions in $O((\log_B K)/(\epsilon \cdot B^{1-\epsilon}))=O((\log_B K)/B^{1-\epsilon})$ amortized I/Os. This data structure uses $O(K)$ space and it can be constructed in $O((K/B) \log_B K)$ I/Os. If the segments are already sorted according to a total order, it can be constructed in $O(K/B)$ I/Os.
\end{theorem}

A major challenge faced by previous multislab structures is how to efficiently support insertions.  At a high-level, it is hard to deal with insertions in cases where a total order is maintained: each time a new segment gets inserted we need to determine its position in the total order, which cannot be done fast. Arge and Vitter~\cite{ArgeV04} developed a deletion-only multislab data structure and then used the so-called logarithmic method~\cite{Bentley79} which allowed them to handle insertions in $O(\log_B^2 K)$ I/Os. Later Arge, Brodal and Rao~\cite{ArgeBR12} developed a more complicated multislab structure supporting insertions in amortized $O(\log_B K)$ I/Os\ by performing separate case analysis depending on the values of $B$.

Here, we support insertions in a much simpler way by breaking each inserted segment into smaller \textit{unit segments} whose endpoints lie on two consecutive vertical lines and can be compared easily to the segments already stored. This way, we are able to support insertions easily in $O(\log_B K)$ I/Os. Finally, we add buffering and obtain sublogarithmic update bounds.

\subsection{Notation and Preliminaries}

\paragraph{{\normalfont{\textbf{External Memory Model.}}}} Throughout this paper we focus on the external memory model of computation. $N$ denotes the number of segments in the planar subdivision, $B$ the block size and $M$ the number of elements that fit in internal memory. We assume that $M \ll N$ and $2 \leq B \leq \sqrt{M}$ (the \emph{tall cache assumption}). It is well-known that sorting $K$ elements requires $\Theta((K/B) \log_{M/B} (K/B))$ I/Os~\cite{AggarwalV88}. Given that $B \leq \sqrt{M} $, this bound is $O((K/B) \log_B K)$. We use this bound for sorting in many places without further explanation.

\paragraph{{\normalfont{\textbf{Ray-shooting Queries.}}}} In the rest of this paper, we focus on answering vertical ray-shooting queries in a dynamic set of non-intersecting line segments. Let $S$ be the set of segments of the polygonal subdivision $\Pi$. Given a query point $p$, the answer to a vertical ray-shooting query is the the first segment of $S$ hit by a vertical ray emanating from a query point in the $(+y)$ direction. It is well-known that if the polygonal subdivision $\Pi$ is connected, a planar point location query for a point $p$ can be answered in $O(\log_B N)$ I/Os after answering a vertical ray-shooting query for $p$\cite{ArgeV04}.

\paragraph{{\normalfont{\textbf{$\ensuremath{B^{\epsilon}}$-Trees.}}}}
All tree structures that we will use are variants of the
$\ensuremath{B^{\epsilon}}$-Trees~\cite{BrodalF03} which are $B$-trees except that the internal nodes have at most $\ensuremath{B^{\epsilon}}$ (and not $B$) children; the leaves still store $\Theta(B)$ data items. For constant $\epsilon$, this does not change the asymptotic height of the tree or the search cost, both remain $O((1/\epsilon) \cdot \log_BN) = O(\log_B N)$.

\end{onlymain}

\section{Overall Structure}
\label{sec:overview}

In this Section we prove Theorem~\ref{thm:main}, using the data structures of Theorems~\ref{lem:left_right} and~\ref{lem:multislab} (detailed in Sections~\ref{sec:left_right} and~\ref{sec:multislab}, respectively).
Given $N$ non-intersecting segments in the plane and a constant $0 < \epsilon \leq 1/2 $, we construct a $O(N)$-space data structure which answers vertical ray-shooting queries in $O( (1/\epsilon)^2 \cdot\log^2_B N) = O(\log^2_B N)$ I/Os\ and supports updates in $O((\log_B N)/(\epsilon \cdot B^{1-\epsilon})) =  O((\log_B N)/B^{1-\epsilon})$ amortized I/Os. Throughout this section we let $\epsilon ' = \epsilon/2$.

\paragraph{{\normalfont{\textbf{The Data Structure.}}}} As in the previous works on planar point location, our primary data structure is based on the \textit{interval tree} (the external interval tree defined in~\cite{ArgeV03}). Our interval tree $\ensuremath{\mathcal{I}}$ is a $\ensuremath{B^{\epsilon '}}$-tree which stores the $x$-coordinates of segment endpoints in its leaves. Here we assume for clarity of presentation that the interval tree is static, i.e. all new segments inserted share $x$-coordinates with already stored segments; in Section~\ref{sec:restucture} we remove this assumption and extend our data structure to accommodate new $x$-coordinates and achieve the bounds of Theorem~\ref{thm:main}.

Each node of $\ensuremath{\mathcal{I}}$ is associated with several secondary structures, as we explain later, and each segment is stored in the secondary structures of exactly one node of $\ensuremath{\mathcal{I}}$. Each node $v$ of $\ensuremath{\mathcal{I}}$ is associated with a vertical slab $s_v$. The slab of the root is the whole plane. For an internal node $v$, the slab $s_v$ is divided into $\ensuremath{B^{\epsilon '}}$ vertical slabs $s_1,\dotsc,s_{\ensuremath{B^{\epsilon '}}}$ corresponding to the children of $v$, separated by vertical lines called \textit{slab boundaries}, such that each slab contains the same number of vertices of $\Pi$.

Let $S$ be the set of segments that compose $\Pi$. Each segment $\sigma \in S$ is stored in the secondary structures associated with the highest node $v$ of $\ensuremath{\mathcal{I}}$ such that $\sigma$ is completely contained in slab $s_v$ and intersects at least one slab boundary partitioning $s_v$. We say that $\sigma$ is \textit{associated with node $v$}.
Segments associated with leaves are stored explicitly in the corresponding leaf. By construction of the slab boundaries, each leaf stores $O(B)$ segments in $O(1)$ blocks.

Consider a segment $\sigma$ associated with node $v$ of $\ensuremath{\mathcal{I}}$. Let $s_{\ell}$ and $s_r$ be the children slabs of $s_v$ where the left and right endpoints of $\sigma$ lie. We call the segment $\sigma \cap s_{\ell}$ the \textit{left subsegment} of $\sigma$, the segment $\sigma \cap s_r$ the \textit{right subsegment} of $\sigma$ and the rest of $\sigma$ (which spans children slabs $s_{\ell+1},\dotsc,s_{r-1}$) is its middle subsegment. See Figure~\ref{fig:slabs-segments} for an illustration.  In this example, the left subsegment is $\sigma \cap s_5$, the right subsegment is $\sigma \cap s_2$, and the portion of $\sigma$ in $s_3$ and $s_4$ is the middle subsegment.

\begin{figure}[t]
\centering
\includegraphics[scale= 0.45]{multislab.pdf}
\caption{The slab of node $v$ of the interval tree $\ensuremath{\mathcal{I}}$ is divided into slabs $s_1,\dotsc,s_6$ corresponding to its children $v_1,\dotsc,v_6$. Segment $\sigma$ is associated with node $v$, with left subsegment in slab $s_2$, right subsegment in $s_5$ and the middle subsegment crosses slabs $s_3,s_4$.}
\label{fig:slabs-segments}
\end{figure}

Let $S_v$ be the set of segments associated with a node $v$ of $\ensuremath{\mathcal{I}}$. To store segments of $S_v$, node $v$ of $\ensuremath{\mathcal{I}}$ contains the following secondary structures:
\begin{comment} (i) a multislab structure $\ensuremath{\mathcal{M}}$ storing the set of middle segments, (ii) $B^{\epsilon}$ left structures $L_i$, for $1 \leq i \leq B^{\epsilon} $, storing the left (sub)segments of slab $s_i$, and (iii) $B^{\epsilon}$ right structures $R_i$, for $1 \leq i \leq B^{\epsilon} $, storing the right (sub)segments of slab $s_i$.  In addition, each internal node $v$ contains an insertion buffer $I_v$ and deletion buffer $D_v$, each storing up to $B$ segments.
\end{comment}

\begin{enumerate
 \item A multislab structure $\ensuremath{\mathcal{M}}$ which stores the set of middle segments.
  \item $\ensuremath{B^{\epsilon '}}$ left structures $L_i$, for $1 \leq i \leq \ensuremath{B^{\epsilon '}} $, storing the left (sub)segments of slab $s_i$.
 \item $\ensuremath{B^{\epsilon '}}$ right structures $R_i$, for $1 \leq i \leq \ensuremath{B^{\epsilon '}} $, storing the right (sub)segments of slab $s_i$.

\end{enumerate}

In addition, each internal node $v$ contains an insertion buffer $I_v$ and deletion buffer $D_v$, each storing up to $B$ segments.

\paragraph{{\normalfont{\textbf{Construction and Space Usage.}}}} Buffers $I_v$ and $D_v$ fit in $O(1)$ blocks. By Theorems~\ref{lem:left_right} and~\ref{lem:multislab}, a secondary structure storing $K$ segments uses $O(K)$ space. Since each segment of $S_v$ is stored in at most 3 secondary structures, overall secondary structures of $v$ use $O(|S_v|)$ space. Thus each node $v$ uses $O(|S_v|)$ space. We get that our data structure uses overall $O(\sum_{v \in \ensuremath{\mathcal{I}}} |S_v|)=O(N)$ space. The interval tree can be constructed in $O((N/B) \log_B N)$ I/Os.
By Theorems~\ref{lem:left_right} and~\ref{lem:multislab}, all secondary structures of a node $v$ of $\ensuremath{\mathcal{I}}$ can be constructed in $O((|S_v|/B) \log_B |S_v|)$ I/Os\ . Thus, all secondary structures of the tree can be constructed in $O((\sum_{v \in \ensuremath{\mathcal{I}}} |S_v|/B) \cdot \log_B N  ) = O((N/B) \log_B N)$ I/Os.

\begin{comment}
\paragraph{{\normalfont{\textbf{Space Usage.}}}} Clearly buffers $I_v$ and $D_v$ fit in $O(1)$ blocks. Theorems~\ref{lem:left_right} and~\ref{lem:multislab} give us that a secondary structure storing $K$ segments uses $O(K)$ space. Since each segment of $S_v$ is stored in at most 3 secondary structures, overall secondary structures of $v$ use $O(|S_v|)$ space. Thus each node $v$ uses $O(|S_v|)$ space. We get that our data structure uses overall $O(\sum_{v \in \ensuremath{\mathcal{I}}} |S_v|)=O(N)$ space.

\paragraph{{\normalfont{\textbf{Construction.}}}} The interval tree can be constructed in $O((N/B) \log_B N)$ I/Os. This can be done by sorting the segments by their endpoints' $x$-coordinates and then determining all slab boundaries to create a balanced interval tree.
By Theorems~\ref{lem:left_right} and~\ref{lem:multislab}, all secondary structures of a node $v$ of $\ensuremath{\mathcal{I}}$ can be constructed in $O((|S_v|/B) \log_B |S_v|)$ I/Os\ . Thus, all secondary structures of the tree can be constructed in $O((\sum_{v \in \ensuremath{\mathcal{I}}} |S_v|/B) \cdot \log_B N  ) = O((N/B) \log_B N)$ I/Os.
\end{comment}
\begin{comment}
\paragraph{{\normalfont{\textbf{Point location queries.}}}}
As defined in Section~\ref{intro}, given a point $p$, a point location query looks to find the nearest segment that is above $p$.  To solve this vertical ray-shooting query, we traverse the interval tree, $\ensuremath{\mathcal{I}}$ from root to leaf, and, at each node $v$ in the path, we:
\begin{enumerate}[(i)]\itemsep.5em
    \item delete any segments that are found within \emph{both} $I_v$ and $D_v$,
    \item check $I_v$ for the nearest segment that is above $p$,
    \item perform the vertical ray-shooting query on each of the secondary structures of $v$, and
    \item flush all deletes in $D_v$ that are assigned to the slab containing $p$.
\end{enumerate}.
During the query, we maintain the nearest segment above $p$ and once we reach the leaf, we explicitly compare $p$ with all of the $B$ segments stored at the leaf to determine the final answer to the point location query.   Thus, we perform vertical ray shooting on $O(\log_B{N})$ secondary structures, insertion and deletion buffers are processed in $O(1)$ I/Os per vertex, and the leaf is evaluated in $O(1)$ I/Os.  In Sections~\ref{sec:left_right} and~\ref{sec:multislab} we show how to perform vertical ray shooting queries on each secondary structure in $O(\log_B{K})$ I/Os, thus the total query time is $O(\log^2_B{K})$.
\end{comment}

\paragraph{{\normalfont{\textbf{Queries.}}}}
To answer a vertical ray-shooting query for a point $p$, we traverse the root-to-leaf path of $\ensuremath{\mathcal{I}}$ based on the $x$-coordinate of $p$, while maintaining a segment $\sigma$ (initialized to \texttt{null}) which is the answer to the query among segments associated with nodes we have traversed so far. At each node $v$ visited along this path, we perform a vertical ray-shooting on each of the secondary structures of $v$ and update $\sigma$ if a closer segment above $p$ is found as a result. Then, we remove all segments that appear in both $I_v$ and $D_v$. Next, we ray-shoot among segments stored in $I_v$ and update $\sigma$ if necessary. Finally, we determine which child $v_i$ of $v$ to visit, and flush any segments of $D_v$ that are contained in the slab of $v_i$ to $D_{v_i}$. We then continue the process at $v_i$.  Once a leaf node is reached, we simply compare the $B$ segments it contains with $p$ and return the closest segment above $p$ among them and $\sigma$.
\begin{comment}
queries in the segments stored in each node of the root-to-leaf path; for the internal nodes we use the secondary structures and for the leaf associated with the slab containing $p$ we perform ray-shooting query by testing all segments explicitly. To answer the ray-shooting query over the entire tree, we return the first segment hit my the vertical ray emanating from $p$ in the $(+y)$ direction, among the $O(\log_B N)$ segments found in the root-to-leaf path.
\end{comment}

\vspace{0.15cm}
\noindent \textit{Bounding the query cost:} Since any root-to-leaf path of $\ensuremath{\mathcal{I}}$
has length $O((1/\epsilon')\cdot \log_B N)$ and each secondary data structure supports ray-shooting queries in $O((1/\epsilon') \cdot\log_B N)$ I/Os\ (due to Theorems~\ref{lem:left_right} and~\ref{lem:multislab}), we
get that a query is answered in $O((1/\epsilon')^2 \cdot \log^2_B N) = O(\log^2_B N)$ I/Os. Note that in each node $v$ of the root-to-leaf path visited, the operations involving $I_v$ and $D_v$ require $O(1)$ I/Os, thus they increase the total cost by at most a $O(1)$ factor.

\paragraph{{\normalfont{\textbf{Insertions.}}}} To handle insertions, we use the insertion buffers stored in nodes of $\ensuremath{\mathcal{I}}$. When a new segment $\sigma$ is inserted, we insert it in the insertion buffer of the root. Let $v$ be an internal node with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon '}}}$. Whenever $I_v$ becomes full, it is flushed. Segments of $I_v$ that cross at least one slab boundary partitioning $s_v$ are inserted in the secondary structures of $v$; segments that are contained in the slab $s_i$ of $v_i$ are inserted in $I_{v_i}$, for $1 \leq i \leq \ensuremath{B^{\epsilon '}}$. In case $I_v$ becomes full for some node $v$ whose children are leaves, we insert those segments explicitly at the corresponding leaves. When a leaf becomes full, we restructure the tree using split operations on full nodes.

\vspace{0.3cm}
\noindent \textit{Bounding the insertion cost:}
We compute the amortized cost of an insertion by considering three components:

\begin{enumerate}[(i)]\itemsep.25em
 \item The cost for moving segments between insertion buffers.  Whenever an insertion buffer $I_v$ gets full, it forwards segments to the buffers of its $\ensuremath{B^{\epsilon '}}$ children performing $O(\ensuremath{B^{\epsilon '}})$ I/Os. Since a flushing occurs every $B$ insertions in $I_v$, the amortized cost of such operations is $O(\ensuremath{B^{\epsilon '}}/B) = O(1/(B^{1-\epsilon'}))$.  Each segment will move in at most $O( (1/\epsilon') \log_B N)$ insertion buffers before it is inserted in the secondary structures of a node (or in a leaf). Thus the amortized cost for moving between buffers is $ O((\log_B N)/(\epsilon' \cdot B^{1-\epsilon'}))$.

 \item The insertion cost in the secondary structures. By Theorems~\ref{lem:left_right} and~\ref{lem:multislab} we get that insertions in secondary structures require $O((\log_B N)/(\epsilon \cdot B^{1-2\epsilon'}))$ I/Os.

 \item The cost of restructuring the tree after insertions when a leaf becomes full. We show in Section~\ref{sec:restucture} that the restructuring requires $O\large(\frac{\log_B N}{\epsilon' \cdot B^{1-\epsilon'}}\large)$ amortized I/Os, by slightly modifying our primary interval tree data structure.
\end{enumerate}
We conclude that our data structure supports insertions in amortized $ O(\log_B N/(\epsilon' \cdot B^{1-2\epsilon'}))  = O(\log_B N/B^{1-\epsilon})$ I/Os.

\paragraph{{\normalfont{\textbf{Deletions.}}}} To support deletions, we use the deletion buffers stored in all nodes of $\ensuremath{\mathcal{I}}$. To delete a segment $\sigma$, we first check whether $\sigma$ is in the insertion buffer $I_r$ of the root $r$ and in that case we delete it; otherwise we store it in $D_r$. Similar to insertions, whenever $D_v$ gets full for some internal node $v$ with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon '}}}$, we flush $D_v$. The segments of $D_v$ crossing at least one slab boundary partitioning $s_v$ are deleted from the corresponding secondary structures associated with $v$; the other segments of $D_v$ are moved to buffers $D_{v_i}$; in case a segment $\sigma$ inserted in $D_{v_i} \cap I_{v_i}$, we delete it from both buffers. In case $D_v$ becomes full for some $v$ parent of leaves, we delete those segments explicitly from the corresponding leaves.

\vspace{0.3cm}
\noindent \textit{Bounding the deletion cost:}
The deletion cost has three components:

\begin{enumerate}[(i)]\itemsep.25em
 \item Moving segments between the deletion buffers. Using the same argument as for insertions, we get
 that this requires$O(\log_B N/(\epsilon' \cdot B^{1-\epsilon'}))$ I/Os, amortized.

 \item The cost of deletion in the secondary structures. By Theorems~\ref{lem:left_right} and~\ref{lem:multislab} we get that deletions in secondary structures require amortized $O(\log_B N/(\epsilon' \cdot B^{1-2\epsilon'}))$ I/Os.

 \item The cost of restructuring the tree. Every $N/2$ deletions, we rebuild the structure using $O((N/B) \log_B N)$ I/Os, to get and amortized restructuring cost of $ O((\log_B N)/B) $ I/Os.

\end{enumerate}
Overall deletions are supported in amortized  $O(\log_B N/(\epsilon' \cdot B^{1-2\epsilon'})) = O(\log_B N/(B^{1-\epsilon}))$ I/Os.

\begin{comment}
\paragraph{{\normalfont{\textbf{Queries in the dynamic structure.}}}} We now show how to support queries in the dynamic case. Let $p$ be the query point and $\rho^{+}$ be the vertical ray emanating from $p$ in the $(+y)$ direction. Similar to the static case, we perform a root-to-leaf search to find the leaf whose slab contains $p$. During this search, while moving from a node $v$ to its child $v_i$ we perform the following updates:

\begin{enumerate}[(i)]\itemsep.5em
 \item For all segments stored in both $I_v$ and $D_v$ (if any), delete them from both buffers.
 \item Find in $I_v$ (resp. $D_v$) the segments which are strictly inside slab $s_i$ corresponding to $v_i$ and move them to $I_{v_i}$ (resp. $D_{v_i}$).
\end{enumerate}
Once we know all nodes of the root-to-leaf path, we perform separate ray-shooting queries on the segments stored in each node. For each node $v$ we do this in two steps. First, we perform ray shooting on the segments stored in the secondary structures of $v$ (same way as in the static case) and then we perform ray shooting among all segments stored in the insertion buffer $I_v$. Among the two segments obtained by those two ray-shooting procedures, we pick the one that is first hit by $\rho^{+}$. This way all relevant insertions/deletions are taken into account. Let $q_v$ be the answer obtained for node $v$. Finally among all segments $q_v$ obtained for nodes $v$ of the root-to-leaf path, we pick the one that is first hit by $\rho^{+}$.

\vspace{0.3cm}
\noindent \textit{Bounding the query cost:} Similar to the static case, queries are supported in $O(\log_B^2 N)$ I/Os. Note that all operations involving insertion/deletion buffers for a node $v$ and its child $v_i$ in the root-to-leaf path can be supported in $O(1)$ I/Os, thus there is no more than $O(1)$ factor overhead compared to the static case.
\end{comment}

\end{onlymain}
\section{Left and Right Structures}
\label{sec:left_right}

In this section we prove Theorem~\ref{lem:left_right}. Given $K$ points all of whose right (left) endpoints lie on a single vertical line, we construct a data structure which answers vertical ray-shooting queries on those segments in $O(\log_B K)$ I/Os\ and supports insertions and deletions in $O((\log_B K)/B^{1-\epsilon})$ amortized I/Os\, for a constant $0 < \epsilon \leq 1/2$.

We describe the structure for the case where we are given a set $\ensuremath{\mathcal{L}}$ of $K$ segments whose right endpoints have the same $x$-coordinate. The case where the left endpoints of the segments have the same $x$-coordinate is completely symmetric. For a segment $\sigma$, we will refer to the $y$-coordinate of its right endpoint as the \textit{$y$-coordinate of $\sigma$}. Conversely we define the \textit{$x$-coordinate of $\sigma$} to be the $x$-coordinate of its left endpoint.

\paragraph{{\normalfont{\textbf{The Data Structure.}}}} We store all segments of $\ensuremath{\mathcal{L}}$ in an augmented B-tree $\ensuremath{\mathcal{T}}$ which supports vertical ray-shooting queries, insertions and deletions. The degree of each node is between $\ensuremath{B^{\epsilon}}/2$ and $\ensuremath{B^{\epsilon}}$, except the root which might have degree in the range $[2,\ensuremath{B^{\epsilon}}]$, and leaves store $\Theta(B)$ elements. For a node $v \in \ensuremath{\mathcal{T}}$, let $\ensuremath{\mathcal{T}}_v$ be the subtree rooted at $v$. Segments are sorted according to their $y$-coordinates. Thus each subtree $\ensuremath{\mathcal{T}}_v$ corresponds to a range of $y$-coordinates, which we call the $y$-range of node $v$. Let $v$ be an internal node of $\ensuremath{\mathcal{T}}$ with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon}}}$. Node $v$ stores the following information:

\begin{enumerate}
\item A buffer of segments $\ensuremath{\mathcal{S}}_v$ of capacity $B$ which contains segments in the $y$-range of $v$ whose left endpoints have the smallest $x$-coordinates (i.e., segments that extend the farthest from the vertical line) and are not stored in any buffer $\ensuremath{\mathcal{S}}_w$ for an ancestor $w$ of $v$. In other words, $\ensuremath{\mathcal{T}}$ together with segments of buffers $\ensuremath{\mathcal{S}}_v$ form an external memory priority search tree~\cite{ArgeSV99}.
\item An insertion buffer $I_v$ and a deletion buffer $D_v$, each storing up to $B$ segments.
\item A list $\ensuremath{\mathcal{M}}_v$ that contains, for each child $v_i$, the segment with minimum $x$-coordinate stored in $\ensuremath{\mathcal{S}}_{v_i}$. We call this the \textit{minimal} segment for child $v_i$.
\end{enumerate}

The data structure satisfies the following invariants: For each node $v \in \ensuremath{\mathcal{T}}$, either $|\ensuremath{\mathcal{S}}_{v}| \geq B/2$ or if $|\ensuremath{\mathcal{S}}_{v}| < B/2$, then $I_v$ and $D_v$ are empty and all buffers stored in descendants $v$ are empty. Also, for each node $v$, buffers $\ensuremath{\mathcal{S}}_v, I_v$ and $D_v$ are disjoint. Finally, for a leaf $v$, $I_v$ and $D_v$ are empty.

\paragraph{{\normalfont{\textbf{Construction and Space Usage.}}}}Overall buffers and lists of each node contain $O(B)$ segments, i.e. they can be stored in $O(1)$ blocks. Thus $\ensuremath{\mathcal{T}}$ can be stored in $O(K/B)$ blocks, i.e. it requires $O(K)$ space. Construction of $\ensuremath{\mathcal{T}}$ requires $O(\frac{K}{B} \log_B K)$ I/Os, since we need to sort all $K$ segments according to their $y$-coordinates. If the segments are already sorted according to their $y$-coordinate, then $\ensuremath{\mathcal{T}}$ can be created in $O(K/B)$ I/Os.

\paragraph{{\normalfont{\textbf{Queries in the static structure.}}}}
To get a feel for how our structure supports queries, we first show how to perform queries in the static case, i.e., assuming there are no insertions and deletions and all buffers $I_v$ and $D_v$ are empty. Later we will give a precise description of performing queries in the fully dynamic structure.

Let $\rho^{+}$ be the ray emanating from $p$ in the $(+y)$ direction and $\rho^{-}$ the ray emanating from $p$ in the $(-y)$ direction. We query the structure by finding the first segment hit by both $ \rho^+$ and $\rho^{-}$. We keep two pointers, $v_+$ and $v_-$, initialized at the root. We also keep the closest segments $\sigma_+$ and $\sigma_-$ seen so far in the $(+y)$ and $(-y)$ direction respectively (initialized to $+ \infty$ and $- \infty$). At each step, we update both $v_+$ and $v_-$ to move from a node of depth $i$ to a node of depth $i+1$. While at level $i$, $v_-$ and $v_+$ might coincide, or one of them might be undefined (set to \texttt{null}).

\end{onlymain}

\begin{comment}
\begin{onlyapp}
\section{Queries in the Left and Right structures.}
~\label{sec:left_right_app}

In this section we discuss in more detail the query algorithm in the left and right structures. Similar to Section~\ref{sec:left_right}, we focus on the case where we are given a set $\ensuremath{\mathcal{L}}$ of $K$ segments whose right endpoints lie on the same vertical line. The notation carries over from Section~\ref{sec:left_right}.

\paragraph{{\normalfont{\textbf{Easy Case: No segments hit by $\rho^{-}$.}}}} We first present the query algorithm for the case where there is no segment hit by $\rho^{-}$. Later we will show why having segments hit by $\rho^{-}$ makes things more complicated and forces some changes to the query algorithm. We keep one pointer $v_+$, initialized at the root, and the closest segment $\sigma$ seen so far, initialized to $\infty$. At each step we do the following: Perform a vertical ray-shooting query from $p$ in the $(+y)$ direction among the segments stored in $\ensuremath{\mathcal{S}}_{v_+}$ and update $\sigma$ if necessary (i.e. if a segment in $\ensuremath{\mathcal{S}}_{v_+}$ is the first segment hit by $\rho^{+}$ among all segments seen so far). Then we have to decide how to continue our search. To do that, we perform a vertical ray-shooting query from $p$ in the $(+y)$ direction among all minimal segments stored in $ v_+ $ (corresponding to the children of $v_+$). Let $v_s$ be the child of $v_+$ containing the first segment hit by $\rho^{+}$ (if such a segment exists). If the $y$-range of $v_s$ is higher than the $y$-coordinate of $\sigma$, or if there is no segment hit by $\rho^{+}$, we stop the search and output $\sigma$. Intuitively in that case all segments stored between $p$ and $\sigma$ are not hit by $\rho^+$, thus $\sigma$ is the answer to the query. Otherwise, we set $v_+ = v_s$, and repeat the same procedure. If $v_+$ is a parent of a leaf and $v_s$ is defined, we perform a vertical ray-shooting query from $p$ in the $(+y)$ direction among all segments of $\ensuremath{\mathcal{S}}_{v_s}$, update $\sigma$ if necessary and output $\sigma$ as the result of the query.

\textit{Correctness:} The correctness of this procedure follows from next lemma.

\begin{lemma}
\label{lem:left_right_query_single}
Assume that at the end of the $i$th step of the query algorithm, $v_+$ exists and let $S_{v_+}$ be the set of segments stored in buffers $\ensuremath{\mathcal{S}}$ in the subtree rooted at $v_+$. Then $\sigma$ is the first segment hit by $\rho^+$ among the segments of $\ensuremath{\mathcal{L}} - S_{v_+}$.
\end{lemma}

\begin{proof}
We prove the lemma by induction.

Base:  At the end of the first step, $v_+$ is a child of the root. We have performed a vertical ray-shooting query among all segments stored at the root and all minimal segments of the children of the root and $\sigma$ is the first segment hit by $\rho^+$ among them. By definition of $v_s$, for any child of the root $v$ with smaller $y$-range than $v_s$, there is no segment stored in the subtree rooted at $v$ hit by $\rho^+$. On the other hand, for any child of the root $v$ with smaller $y$-range than $v_s$, we know that $\sigma$ is below all segments stored in the subtree rooted at $v$, due to the fact that $\rho^{+}$ hit a segment in $v_s$. Thus $\sigma$ is the first segment hit by $\rho^{+}$ among the segments of $\ensuremath{\mathcal{L}} - S_{v_+}$.

Induction step: Assume the lemma holds at step $i$, i.e. we have a $v_+$ at level $i$ and $\sigma$ is the first segment hit by $\rho^+$ among all segments in $\ensuremath{\mathcal{L}} - S_{v_+}$. Now we perform a vertical ray-shooting query among segments stored in $\ensuremath{\mathcal{S}}_{v_+}$ and all minimal segments stored in $v_+$, and update $\sigma$ if necessary. Let $v_s$ be the child containing the first minimal segment of $v_+$ hit by $\rho^+$ (if such a segment exists). That means, for all children $v$ of $v_+$ with $y$-range smaller than the $y$-range of $v_s$, there is no segment in the subtree rooted at $v$ intersecting $\rho^{+}$. Also, by definition of $v_s$, for all children $v$ of $v_+$ with larger $y$-range than $v_s$, we have that $\sigma$ is below all segments stored in $\ensuremath{\mathcal{T}}_v$. Combining this with the induction argument, we get that $\sigma$ is the first segment hit by $\rho^{+}$ among all segments of $\ensuremath{\mathcal{L}} - S_{v_s}$. Since for level $i+1$ we set $v_+ = v_s$, the lemma
follows.

\end{proof}

Correctness of the query procedure is now clear: If at each step $v_+$ is defined, then we reach a leaf $v_s$ with the property that $\sigma$ is the first segment hit by $\rho^{+}$ among segments of $\ensuremath{\mathcal{L}} - \ensuremath{\mathcal{S}}_{v_s}$. By checking all segments of $\ensuremath{\mathcal{S}}_{v_s}$ and updating $\sigma$ if necessary, we make sure that $\sigma$ the first segment hit by $\rho^{+}$ among segments of $\ensuremath{\mathcal{L}}$.

On the other hand, let $i$ be the level where $v_+$ is defined for last time. That means, at level $i+1$, $v_s$ is not defined. Then for each child $v$ of there is no segment hit by $\rho^{+}$ stored in any buffer $\ensuremath{\mathcal{S}}$ in the subtree rooted at $v$. Recall that by Lemma~\ref{lem:left_right_query_single}, $\sigma$ is the first segment hit by $\rho^+$ among the segments $\ensuremath{\mathcal{L}} - S_{v_+}$. Since we perform ray shooting query among all segments stored in the buffer of $v_+$ and update $\sigma$ if necessary, and there is no other segment hit by $\rho^+$ stored in any other buffer of $\ensuremath{\mathcal{T}}_{v_+}$, we get that the current $\sigma$ is the is the first segment hit by $\rho^+$ among the segments $\ensuremath{\mathcal{L}}$ and the search ends correctly.

\paragraph{{\normalfont{\textbf{General Case.}}}}
However, this is not enough to answer vertical ray-shooting queries in general. In fact, if $\rho^-$ hits a segment, it might be that the procedure above gives a wrong output. See figure. We might set $v_+$ to be a different node than the one containing the first segment hit by $\rho^{+}$ in its subtree. Elaborate.

For completeness, we describe again the query algorithm for the general case, and prove Lemma~\ref{lem:left_right_query_general} which implies the correctness of the algorithm.

\end{onlyapp}
\end{comment}

\begin{onlymain}

We now describe the query algorithm.  We start at the root of $\ensuremath{\mathcal{T}}$ and advance down, while updating $v_+$, $v_-$, and $\sigma_+$,$\sigma_-$. When at depth $i$, we find the first segment $\sigma_i$ hit by $\rho^{+}$ among $\ensuremath{\mathcal{S}}_{v_-}$ and $\ensuremath{\mathcal{S}}_{v_+}$ and update $\sigma_+$ if necessary (i.e. if $\sigma_i$ is the first segment hit by $\rho^{+}$ among all segments seen so far). Similarly, we ray-shoot on $\rho^{-}$ among $\ensuremath{\mathcal{S}}_{v_-}$ and $\ensuremath{\mathcal{S}}_{v_+}$ and update $\sigma_-$ if necessary. To determine in which nodes of depth $i+1$ to continue the search, we ray-shoot on $\rho^+$ and $\rho^{-}$ among $\ensuremath{\mathcal{M}}_{v_-}$ and
$ \ensuremath{\mathcal{M}}_{v_+} $ (i.e., all minimal segments of children of $v_-$ and $v_+$). Let $v_s$ be the node containing the first segment $\sigma_{m+}$ hit by $\rho^{+}$ (if $\sigma_{m+}$ exists). If the $y$-range of $v_s$ is higher than the $y$-coordinate of $\sigma_+$ or if $\sigma_{m+}$ does not exist, we leave $v_+$ undefined for level $i+1$. Otherwise, we set $v_+ = v_s $. Similarly, let $v_p$ be the node containing the first minimal segment $\sigma_{m-}$ hit by $\rho^{-}$ (if such a segment exists). If the $y$-range of $v_p$ is lower than the $y$-coordinate of $\sigma_-$ or if $\sigma_{m-}$ does not exist, we leave $v_-$ undefined for level $i+1$. Otherwise we set $v_- = v_p$.

If both $v_+$ and $v_-$ are undefined for the next level $i+1$, we stop the procedure and output $\sigma_+$ as the result to the vertical ray-shooting query. Otherwise we repeat the same procedure in the next level. When we reach a leaf level, we find the first segment hit by $\rho^{+}$ among $\ensuremath{\mathcal{S}}_{v_-}$ and $\ensuremath{\mathcal{S}}_{v_+}$, update $\sigma+$ if necessary, and output $\sigma+$ as the result of the query.

\begin{figure}[t]
\centering
\includegraphics[scale= 0.45]{left_right_query.pdf}
\caption{Example of the query algorithm in the left structure: Left column shows the segments stored in $\ensuremath{\mathcal{T}}$, the query point $p$ and the vertical ray $\rho$ emanating from $p$. Right column shows buffers $\ensuremath{\mathcal{S}}$ of the nodes of $\ensuremath{\mathcal{T}}$. Red segments are stored in the root. For nodes $u,v,w$, the green segment is their minimal segment, i.e., the one stored in list $\ensuremath{\mathcal{M}}_r$. By ray-shooting on $\rho$ among green segments, the first segment hit upwards is $\sigma_5$, which is stored in $\ensuremath{\mathcal{S}}_w$, thus we set $v_+ = w$. Note that $\sigma_2$ (the correct answer for the query) is not stored in $\ensuremath{\mathcal{S}}_w$, i.e., maintaining only $v_+$ produces an incorrect answer. Thus, our algorithm ray-shoots downwards as well, hitting $\sigma_1$, which is stored in $u$, and setting $v_- = u$. Then, by ray-shooting on $\rho$ among $\ensuremath{\mathcal{S}}_u$ and $\ensuremath{\mathcal{S}}_w$, the first segment we hit upwards of $p$ is $\sigma_2$.}
\label{fig:left_right_query}
\end{figure}

\vspace{0.1cm}
\textit{Remark:} The reader might wonder why we answer vertical ray-shooting queries in both directions and keep two pointers $v_-$ and $v_+$. Isn't it sufficient to answer queries in one direction and keep one pointer at each step? Figure~\ref{fig:left_right_query} shows an example where this is not true and maintaining only the $v_+$ pointer would result in an incorrect answer.

The formal proof of correctness of this query algorithm is deferred to Appendix~\ref{sec:left_right_app}.

\end{onlymain}

\begin{onlyapp}
\section{Queries in the Left and Right Structures.}
~\label{sec:left_right_app}

In this Section we show the correctness of the query algorithm of the static left (right) structure presented in Section~\ref{sec:left_right}.

\vspace{0.1cm}

\textit{Correctness:}
The correctness of the query algorithm follows from the next lemma. For a node $v \in \ensuremath{\mathcal{T}}$ let $S_{v}$ be the set of segments stored in buffers $\ensuremath{\mathcal{S}}$ in $\ensuremath{\mathcal{T}}_v$ .

\begin{lemma}
\label{lem:left_right_query_general}
Assume that at the end of the $i$th step of the query algorithm, either $v_+$ or $v_-$ is defined. Then $\sigma_+$ is the first segment hit by $\rho^+$ among the segments of $\ensuremath{\mathcal{L}} - (S_{v_-} \cup S_{v_+})$.
\end{lemma}

\begin{proof}
We prove the lemma by induction.

\vspace{0.1cm}

\textit{Induction Base:} At the end of the first step, $v_+$ and $v_-$ are children of the root $r$ and $\sigma_+$ is the first segment hit by $\rho^+$ among all segments stored at the root (in $\ensuremath{\mathcal{S}}_r$ and $\ensuremath{\mathcal{M}}_r$). By definition of $v_s = v_+$, for any child of the root $v$ with higher $y$-range than $v_+$, $\sigma$ is below all segments of $S_{v}$. Similarly, for any child of the root $v'$ with smaller $y$-range than $v_-$ (if $v_-$ exists), there is no segment in $S_{v'}$ hit by $\rho^+$ (since there exists a segment in $\ensuremath{\mathcal{S}}_{v_-}$ hit by $\rho^-$). Finally, for any child $v''$ of the root whose $y$-range is between the range of $v_-$ and $v_+$, by definition of $v+$, there is no segment in $S_{v''}$ hit by $\rho^{+}$. We conclude that $\sigma$ is the first segment hit by $\rho^+$ among the segments in $\ensuremath{\mathcal{L}} - (S_{v_-} \cup S_{v_+})$.

\vspace{0.1cm}

\textit{Inductive Step:} Assume the lemma holds at the end of step $i$, i.e. we have at least one of $v_+$ and $v_-$ at level $i$ and $\sigma_+$ is the first segment hit by $\rho^+$ among all segments in $\ensuremath{\mathcal{L}} - (S_{v_+} \cup S_{v_+} )$.

During $(i+1)$th step we ray-shoot on $\rho^{+}$ among segments stored in $\ensuremath{\mathcal{S}}_{v_+}, \ensuremath{\mathcal{S}}_{v_+}, \ensuremath{\mathcal{M}}_{v_+}$ and $\ensuremath{\mathcal{M}}_{v_-}$, and update $\sigma_+$ if necessary. Let $v_s$ be the node containing the first segment hit by $\rho^+$ among $\ensuremath{\mathcal{M}}_{v_+}$ and $\ensuremath{\mathcal{M}}_{v_-}$ (if such a segment exists). Let also $v_p$ be the node containing the first segment hit by $\rho^-$ among $\ensuremath{\mathcal{M}}_{v_+}$ and $\ensuremath{\mathcal{M}}_{v_-}$ (if such a segment exists).

 By definition of $v_s $, for any node $v$ which is a child of $v_-$ or $v_+$ with higher $y$-range than $v_s$, $\sigma_+$ is below all segments of $S_{v}$. Similarly, for a node $v'$ which is a child of $v_-$ or $v_+$ with smaller $y$-range than $v_p$ (if $v_p$ exists), there is no segment of $S_{v'}$ hit by $\rho^+$ (since there exists a segment in $\ensuremath{\mathcal{S}}_{v_p}$ hit by $\rho^-$). Finally, for any child $v''$ of $v_-$ or $v_+$ whose $y$-range is between the range of $v_-$ and $v_+$, by definition of $v+$, there is no segment in $S_{v''}$ hit by $\rho^{+}$.

 Recall that by the induction hypothesis $\sigma_+$ at the end of the previous step was the first segment hit by $\rho^+$ among segments of $ \ensuremath{\mathcal{L}} - (S_{v_+} \cup S_{v_+})$. Now we updated $\sigma_+$ and showed that there is no segment hit by $\rho^{+}$ before $\sigma_+$ in any subtree other than $\ensuremath{\mathcal{T}}_{v_s}$ or $\ensuremath{\mathcal{T}}_{v_p}$. We conclude that $\sigma$ is the first segment hit by $\rho^+$ among the segments in $\ensuremath{\mathcal{L}} - (S_{v_s} \cup S_{v_p})$. Since at the end of the $(i+1)$th step we set $v_- = v_p$ and $v_+ = v_s$, the lemma follows.

\end{proof}

We now explain how Lemma~\ref{lem:left_right_query_general} implies the correctness of the query algorithm. To see that, let $i$ be the last level where either $v_+$ or $v_-$ is defined; at the beginning of the query algorithm at level $i$, $\sigma_+$ is the first segment hit by $\rho^{+}$ among segments of $\ensuremath{\mathcal{L}} - (S_{v_-} \cup S_{v_+})$. Moreover at the end of this step, both $v_s$ and $v_p$ are not defined, i.e., for each child $v$ of $v_-$ or $v_+$ there is no segment in $S_v$ hit by $\rho^{+}$ before $\sigma_+$. Since $S_{v_-} \cup S_{v_+} = \ensuremath{\mathcal{S}}_{v_-} \cup \ensuremath{\mathcal{S}}_{v_+} \cup (\cup_{v} S_v) $, we get that $\sigma_+$ is the first segment hit by $\rho^{+}$ among segments of $\ensuremath{\mathcal{L}} - (\ensuremath{\mathcal{S}}_{v_-} \cup \ensuremath{\mathcal{S}}_{v_+})$. By checking all segments of $\ensuremath{\mathcal{S}}_{v_-} \cup \ensuremath{\mathcal{S}}_{v_+}$ and updating $\sigma_+$ if necessary, we make sure that $\sigma_+$ is the first segment hit by $\rho^{+}$ among segments of $\ensuremath{\mathcal{L}}$.

\end{onlyapp}

\begin{onlymain}
\vspace{0.1cm}

\textit{Bounding the query cost:} To count the cost, observe that in each step we move down the tree by one level and perform operations that require $O(1)$ I/Os, as we check $O(B)$ segments stored in the current nodes $v_-$ and $v_+$. Since the height of the tree is $O((1/\epsilon) \log_B K)$, a query is answered in $ O((1/\epsilon) \log_B K)) = O(\log_B K)$ I/Os.

\paragraph{{\normalfont{\textbf{Insertions.}}}}
Assume we want to insert a segment $\sigma$ into the left structure $\ensuremath{\mathcal{L}}$. If the $x$-value of $\sigma$ is smaller than the maximum $x$-value of a segment stored in the buffer of the root $\ensuremath{\mathcal{S}}_r$, we insert $\sigma$ into $\ensuremath{\mathcal{S}}_r$. Otherwise we store $\sigma$ in the insertion buffer of the root $I_r $. Note that insertion of $\sigma$ in $\ensuremath{\mathcal{S}}_r$ might cause $\ensuremath{\mathcal{S}}_r$ to overflow (i.e., $|\ensuremath{\mathcal{S}}_r| = B+1 $); in that case we move the segment of $\ensuremath{\mathcal{S}}_r$ with the maximum $x$-value into the insertion buffer of the root $I_{r}$.

 Let $v$ be an internal node with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon}}}$. Whenever the insertion buffer $I_v$ becomes full, we \textit{flush} it, moving the segments to buffers of the corresponding children. For a segment $\sigma$ that should be stored in child $v_i$, we repeat the same procedure as in the root: Check whether $\sigma$ has smaller $x$-value than the maximum $x$-value of a segment stored in $\ensuremath{\mathcal{S}}_{v_i}$ and if yes, store $\sigma$ in $\ensuremath{\mathcal{S}}_{v_i}$, otherwise store it in $I_{v_i}$. If $\ensuremath{\mathcal{S}}_{v_i}$ overflows, we move its last segment (i.e. the one with maximum $x$-value) into $I_{v_i}$. Also, if $\sigma$ gets stored in $\ensuremath{\mathcal{S}}_{v_i}$ and its $x$-value is smaller than all previous segments of $\ensuremath{\mathcal{S}}_{v_i}$, we update the minimal segment of $v_i$, $\ensuremath{\mathcal{M}}_{v}$.

 When $\ensuremath{\mathcal{S}}_v$ overflows for some leaf $v$, we split $v$ into two leaves $v_1$ and $v_2$, as in standard $B$-trees. Note that this might cause recursive splits of nodes at greater height.

\vspace{0.15cm}
\noindent \textit{Bounding the insertion cost:} To flush a buffer $I_v$ and forward segments to buffers $\ensuremath{\mathcal{S}}_{v_i}$ and $I_{v_i}$, for $1\leq i \leq \ensuremath{B^{\epsilon}}$ we perform $O(\ensuremath{B^{\epsilon}})$ I/Os. Since $I_v$ becomes full after at least $B$ insertions, the amortized cost of moving a segment from $I_v$ to buffers of a child of $v$ is $O(\ensuremath{B^{\epsilon}}/B) = O(1/B^{1-\epsilon})$. Each inserted segment moves between buffers in a root-to-leaf path of length $O((1/\epsilon) \log_B K)$, thus the total amortized cost for moves between buffers is $O(\log_B K/(\epsilon \cdot B^{1-\epsilon}))$ I/Os. The restructuring of $\ensuremath{\mathcal{T}}$ due to splitting nodes requires amortized $O(1/B)$ I/Os, as in standard  B-trees. Thus, insertions are supported in $ O(\log_B K/(\epsilon \cdot B^{1-\epsilon})) $ amortized I/Os.

\paragraph{{\normalfont{\textbf{Deletions.}}}} To delete a segment $\sigma$, we first check whether it is stored in the buffers of the root $\ensuremath{\mathcal{S}}_r$ or $I_r$; in this case we delete it. Otherwise, we insert $\sigma$ in the deletion buffer of the root $D_r$.

Let $v$ be an internal node with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon}}}$. Whenever $D_v$ becomes full we flush it and move the segments to the corresponding children and repeat the same procedure: For a segment $\sigma$ which moves to child $v_i$, we check whether it is stored in $\ensuremath{\mathcal{S}}_{v_i}$ or $I_{v_i}$: if yes, we delete it and update the minimal segment of $v_i$ in $\ensuremath{\mathcal{M}}_v$ if necessary. Otherwise, we store $\sigma$ in the deletion buffer $D_{v_i}$. If segment buffer $\ensuremath{\mathcal{S}}_{v}$ underflows (i.e., $| \ensuremath{\mathcal{S}}_{v} | < B/2 $), we refill it using segments stored in buffers $\ensuremath{\mathcal{S}}_{v_i}$; the segments moved to $\ensuremath{\mathcal{S}}_{v}$ are deleted from $\ensuremath{\mathcal{S}}_{v_i}$ and all necessary updates in $\ensuremath{\mathcal{M}}_{v}$ are performed. This might cause underflowing segment buffers $\ensuremath{\mathcal{S}}_{v_i}$ for children of $v_i$; we handle those in the same way. In case all buffers $\ensuremath{\mathcal{S}}_{v_i}$ become empty and $| \ensuremath{\mathcal{S}}_{v} | < B$ , we move the segments from $I_v$ to $\ensuremath{\mathcal{S}}_v$ until either $| \ensuremath{\mathcal{S}}_{v} | = B$ or $| I_v | = 0$.

\vspace{0.15cm}
\noindent \textit{Bounding the deletion cost:} Deletion cost consists of three components:

\begin{enumerate}[(i)]\itemsep.25em
\item Cost for moving segments between buffers: Using the same analysis as for insertions we get that this requires $O(\log_B K/(\epsilon \cdot B^{1-\epsilon})) $ amortized I/Os.
\item Cost due to refilling of buffers $\ensuremath{\mathcal{S}}_{v}$: For a node $v$ with children $v_i$, while refilling buffer $\ensuremath{\mathcal{S}}_{v}$ from $\ensuremath{\mathcal{S}}_{v_i}$ we perform $O(\ensuremath{B^{\epsilon}})$ I/Os\ and we move $\Theta(B)$ segments one level higher. Thus the amortized cost of moving a segment up by one level is $O(1/B^{1-\epsilon})$. Since the tree has height $O((1/\epsilon) \cdot \log_B K)$, over a sequence of $K$ deletions the total number of moves of segments by one level is $O((1/\epsilon) \cdot K \cdot \log_B K)$. Thus the total cost due to refilling is at most $O( (1/ \epsilon B^{1-\epsilon}) K \cdot \log_B K)$, which implies that the amortized cost is $O(\log_B K/(\epsilon \cdot B^{1-\epsilon}))$.

A corner case that we did not take into account above is when the total number of segments stored in buffers $\ensuremath{\mathcal{S}}_{v_i}$ are less than $B/2$. In this case it is not valid that the amortized cost of updating $\ensuremath{\mathcal{S}}_{v}$ is $O(\ensuremath{B^{\epsilon}}/B)$. To take care of this, we use a simple amortization trick: we double charge all I/Os\ performed relating to insertions.  This way, for each buffer $\ensuremath{\mathcal{S}}_{v_i}$ there is a saved I/O\ from the time when segments move from $I_v$ to node $v_i$. We use this additional saved
I/O\ when $\ensuremath{\mathcal{S}}_{v_i}$ gets emptied due to the refilling of $S_{v}$.

\item Restructuring requires $O(\frac{\log_B K}{B})$ amortized I/Os, by rebuilding the structure after $K/2$ deletions.
\end{enumerate}

Overall, the amortized deletion cost is $O(\log_B K/(\epsilon \cdot B^{1-\epsilon})) =O(\log_B K/B^{1-\epsilon})$ I/Os.

\paragraph{{\normalfont{\textbf{Queries in the dynamic structure.}}}}
We now describe how to extend our query algorithm to the dynamic case.
In order to ensure that all nodes visited are up-to-date and we do not miss any updates in the insertion/deletion buffers, when moving a pointer from a node $u$ to its child $v_i$, we flush any deletes in $D_{u}$ to $v_i$, i.e. delete segments of $D_u$ that are stored in $\ensuremath{\mathcal{S}}_{v_i}$, store the other segments in $D_{v_i}$ and update $\ensuremath{\mathcal{M}}_u$ if necessary. We then delete any segments found in both $I_{v_i}$ and $D_{v_i}$. Finally, we compare segments in $I_{v_i}$ with $\sigma_+$ (recall this is the first segment hit by $\rho^{+}$ among segments considered so far) and, if any segment in $I_{v_i}$ would be hit by $\rho^{+}$ before $\sigma_+$ we replace $\sigma_+$ with it. Clearly this increases the total cost by at most a $O(1)$ factor compared to the static case, thus the query cost is $O((1/\epsilon)\log_B K)$ I/Os.

\end{onlymain}

\section{Multislab Structure}
\label{sec:multislab}

In this section we prove Theorem~\ref{lem:multislab}. Assume that we are given a set of $K$ non-intersecting segments with endpoints on at most $\ensuremath{B^{\epsilon /2}}+1$ vertical lines $l_1,\dotsc,l_{\ensuremath{B^{\epsilon /2}}+1}$, for some constant $O < \epsilon \leq 1/2$. We show that those segments can be stored in a data structure which uses $O(K)$ space, supports vertical ray-shooting queries in $ O(\log_B K)$ I/Os, and updates in $ O(\log_B K/B^{1-\epsilon})$ amortized I/Os, for $0 < \epsilon \leq 1/2$. This data structure can be constructed in $O((K/B) \log_{B}K)$ I/Os. We call this data structure a \textit{multislab} structure.

\begin{comment}
A major challenge faced by previous multislab structures is how to efficiently perform insertions.  At a high-level, it is hard to deal with insertions in cases where a total order is maintained: each time a new segment gets inserted we need to determine its position in the total order, which can not be done fast. Arge and Vitter~\cite{ArgeV04} developed a deletion-only multislab data structure and then used the so-called logarithmic method~\cite{Bentley79} which allowed them to handle insertions in $O(\log_B^2 K)$ I/Os. Later Arge, Brodal and Rao~\cite{ArgeBR12} developed a more complicated multislab structure supporting insertions in amortized $O(\log_B K)$ I/Os\ by performing separate case analysis depending on the values of $B$.

Here, we support insertions in a much simpler way, by breaking each inserted segment into smaller \textit{unit segments} which can be compared easily to the segments that we have already stored. This way, we are able to support insertions easily in $O(\log_B K)$ I/Os. Finally, we add buffering  and obtain sublogarithmic update bounds.
\end{comment}
For notational convenience we set $\epsilon' = \epsilon/2$. This way endpoints of the segments lie on at most $\ensuremath{B^{\epsilon '}} +1$ vertical lines $l_1,\dotsc,l_{\ensuremath{B^{\epsilon '}}+1}$.  For $1 \leq i \leq \ensuremath{B^{\epsilon '}}$, let $s_i$ denote the vertical slab defined by vertical lines $l_i$ and $l_{i+1}$.
We will show that queries are supported in $O(\log_B K)$ I/Os\ and updates in $O((\log_B K) / B^{1-2\epsilon '})$ I/Os . Theorem~\ref{lem:multislab} then follows.

\paragraph{{\normalfont{\textbf{Total Order.}}}} In order to implement the multislab structure we need to maintain an ordering of the segments based on their $y$-coordinates. Using standard approaches (see e.g.~\cite{ArgeV04,ArgeBR12}) we can define a partial order for segments that can be intersected by a vertical line. Arge et. al.~\cite{ArgeVV07} showed how to extend a partial order into a total order on $K$ segments (not necessarily all intersecting the same vertical line) in $O((K/B) \log_{M/B}\frac{K}{B}) = O((K/B) \log_{B}K)$ I/Os. We use this total order to create our multislab structure.

\paragraph{{\normalfont{\textbf{The Data Structure.}}}}
We store the ordered segments in an augmented B-tree \ensuremath{\mathcal{T}} which supports queries, insertions and deletions. The degree of each node is between $\ensuremath{B^{\epsilon '}} /2$ and $\ensuremath{B^{\epsilon '}}$, except the root which might have degree in the range $[2,\ensuremath{B^{\epsilon '}}]$. Leaves store $\Theta(B)$ elements. For a node $v \in T$, let $\ensuremath{\mathcal{T}}_v$ be the subtree rooted at $v$. Let $v_1,\dotsc,v_{\ensuremath{B^{\epsilon '}}}$ be the children of an internal node $v$. Node $v$ stores the following information:

\begin{enumerate}\itemsep.25em
 \item A buffer $\ensuremath{\mathcal{S}}_v$ of capacity $B$ which contains the highest (according to the total order) segments stored in $\ensuremath{\mathcal{T}}_v$ which are not stored in any buffer $\ensuremath{\mathcal{S}}_w$ for an ancestor $w$ of $v$. In other words, $\ensuremath{\mathcal{T}}$ together with segments of buffers $\ensuremath{\mathcal{S}}_v$ form an external memory priority search tree~\cite{ArgeSV99}.
 \item An insertion buffer $I_v$ and a deletion buffer $D_v$, both storing up to $B$ segments.

 \item A list $L_v$ which contains, for each slab $s_i$, $1 \leq i\leq \ensuremath{B^{\epsilon '}}$, and each child $v_j$, $1 \leq j\leq \ensuremath{B^{\epsilon '}}$, the highest segment (according to the total order) $t_{i,j}$ crossing slab $s_i$ stored in $\ensuremath{\mathcal{T}}_{v_j}$.
\end{enumerate}

The data structure satisfies the following invariants: i) for each node $v \in \ensuremath{\mathcal{T}}$, either $|\ensuremath{\mathcal{S}}_{v}| \geq B/2$ or if $|\ensuremath{\mathcal{S}}_{v}| < B/2$, then $I_v$ and $D_v$ are empty and all buffers of descendants $w$ of $v$ are empty, ii) for each node $v$, buffers $\ensuremath{\mathcal{S}}_v, I_v$ and $D_v$ are disjoint, and iii) for every leaf $v$, $I_v$ and $D_v$ are empty.

\paragraph{{\normalfont{\textbf{Construction and Space Usage.}}}}Overall buffers of each node contain $O(B)$ segments and list $L_v$ contains at most $B^{2\epsilon'} = O(B)$ segments, i.e., they can be stored in $O(1)$ blocks. Thus $\ensuremath{\mathcal{T}}$ can be stored in $O(K/B)$ blocks, i.e. it requires $O(K)$ space. The structure can be constructed in $O(\frac{K}{B} \log_B K)$ I/Os. If segments are already sorted according to a total order, construction requires $O(K/B)$ I/Os.

\end{onlymain}

\begin{onlyapp}
\section{Updates in the Multislab Structure}
\label{sec:multislab_app}
In this section we present all details on how our multislab structure supports insertions and deletions.
\end{onlyapp}

\paragraph{{\normalfont{\textbf{Insertions.}}}} To insert a new segment $\sigma$ we need to determine its position in the total order. Clearly, we can not afford to produce a new total order from scratch, as this costs $O((K/B) \log_{B}K)$ I/Os. Thus, we break $\sigma$ into at most $\ensuremath{B^{\epsilon '}}$ \textit{unit segments}, where each segment crosses exactly one slab. In particular, if $\sigma$ crosses slabs $s_{\ell},\dotsc,s_r$, we break it into unit segments $\sigma_{\ell},\dotsc,\sigma_r$, where segment $\sigma_i$ crosses slab $s_i$. We call all such unit segments stored in $\ensuremath{\mathcal{T}}$ \textit{new} segments. The rest of the segments stored in $\ensuremath{\mathcal{T}}$ are called the \textit{old} segments of $\ensuremath{\mathcal{T}}$. Now we can easily update the total order: segment $\sigma_i$ needs to be compared only with segments crossing slab $s_i$; if $\sigma_p$ and $\sigma_s$ are the predecessor and successor of $\sigma_i$ within slab $s_i$, we locate $\sigma_i$ in an arbitrary position between $\sigma_p$ and $\sigma_s$ in the total order. This way a valid total order is always maintained.

\begin{onlymain}
We now describe the insertion algorithm. When segment $\sigma $ needs to be inserted, we first break it into unit segments $\sigma_{\ell},\dotsc,\sigma_r$. For each segment $\sigma_j$, $\ell \leq j \leq r$, we first check whether it should be inserted in the buffer $\ensuremath{\mathcal{S}}_r$ of the root: if this is the case we store it there; otherwise we store it in the insertion buffer of the root $I_r$. In case $\ensuremath{\mathcal{S}}_{r} $ overflows (i.e. $|\ensuremath{\mathcal{S}}_{r}| = B+1$) we move its last segment (according to the total order) to $I_{r}$. Let $v$ be an internal node with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon '}}}$. Each time $I_v$ becomes full, we \textit{flush} it and move the segments to its children $v_i$, for $1 \leq i \leq \ensuremath{B^{\epsilon '}}$. For a segment moving from $v$ to $v_i$, we first check whether it is greater (according to the total order) than the minimum segment stored in $\ensuremath{\mathcal{S}}_{v_i}$ and if so we store it in $\ensuremath{\mathcal{S}}_{v_i}$; otherwise we store it in buffer $I_{v_i}$. In case $\ensuremath{\mathcal{S}}_{v_i} $ overflows (i.e. $|\ensuremath{\mathcal{S}}_{v_i}| = B+1$) we move its last segment to $I_{v_i}$. Also we update information in list $L_v$ if necessary. In case $I_{v_i}$ becomes full, we repeat the same procedure recursively.

When $\ensuremath{\mathcal{S}}_v$ overflows for some leaf $v$, we split $v$ into two leaves $v_1$ and $v_2$, as in standard $B$-trees. Note that this might cause recursive splits of nodes at greater height.

\vspace{0.15cm}

\noindent \textit{Bounding the insertion cost:} To flush a buffer $I_v$ and move segments to buffers of child nodes $\ensuremath{\mathcal{S}}_{v_i}$ and $I_{v_i}$, we need to perform $O(\ensuremath{B^{\epsilon '}})$ I/Os. Since each segment breaks into at most $\ensuremath{B^{\epsilon '}}$ unit segments, a buffer of size $B$ becomes full after at least $B/ \ensuremath{B^{\epsilon '}} = B^{1-\epsilon'}$ insertions. Thus the amortized cost of moving a segment from a buffer of depth $i$ to depth $i+1$ is $O(\ensuremath{B^{\epsilon '}}/{B^{1-\epsilon'}}) = O(1/B^{1-2\epsilon'})$. Since each segment will be eventually stored in a node of depth $O((1/\epsilon') \cdot \log_B K)$, the amortized cost until it gets inserted is $O(\log_B K/(\epsilon ' \cdot B^{1-2\epsilon'}))$.  The restructuring of $\ensuremath{\mathcal{T}}$ due to splitting full nodes requires amortized $O(1)$ I/Os, as in standard B-trees. Overall insertions require $O(\log_B K/(\epsilon \cdot B^{1-2\epsilon'}) ) = O((\log_B K)/B^{1-\epsilon} ) $ amortized I/Os.

\begin{comment}
\vspace{0.15cm}
\noindent \textit{Bounding the insertion cost:} The analysis of the insertion cost is quite similar to the one in the data structure of Section~\ref{sec:left_right} and is deferred to Appendix~\ref{sec:multislab_app}. We get that the amortized insertion cost for each unit segment inserted is $O(\log_B K/ B^{1-\epsilon'})$ I/Os. Since each inserted segment leads to at most $\ensuremath{B^{\epsilon '}}$ insertions of unit segments, we get that the amortized insertion cost is $ O(\log_B K/B^{1-2\epsilon'})$ I/Os.
\end{comment}
\end{onlymain}

\begin{comment}
\begin{onlyapp}

We now describe the insertion algorithm. When segment $\sigma $ needs to be inserted, we first break it into unit segments $\sigma_{\ell},\dotsc,\sigma_r$. For each segment $\sigma_j$, $1 \leq j \leq \ensuremath{B^{\epsilon}}$, we first check whether it should be inserted in the buffer $\ensuremath{\mathcal{S}}_r$ of the root: if this is the case we store it there; otherwise we store it in the insertion buffer of the root $I_r$. In case $\ensuremath{\mathcal{S}}_{r} $ overflows (i.e. $|\ensuremath{\mathcal{S}}_{r}| = B+1$) we move its last segment to $I_{r}$. Let $v$ be an internal node with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon '}}}$. Each time $I_v$ becomes full, we \textit{flush} it and move the segments to its children $v_i$, for $1 \leq i \leq \ensuremath{B^{\epsilon '}}$. For a segment moving from $v$ to $v_i$, we first check whether it is greater (according to the total order) than the minimum segment stored in $\ensuremath{\mathcal{S}}_{v_i}$ and if so we store it in $\ensuremath{\mathcal{S}}_{v_i}$; otherwise we store it in buffer $I_{v_i}$. In case $\ensuremath{\mathcal{S}}_{v_i} $ overflows (i.e. $|\ensuremath{\mathcal{S}}_{v_i}| = B+1$) we move its last segment to $I_{v_i}$. Also we update information in list $L_v$ if necessary. In case $I_{v_i}$ becomes full, we repeat the same procedure recursively.

When $\ensuremath{\mathcal{S}}_v$ overflows for some leaf $v$, we split $v$ into two leaves $v_1$ and $v_2$, as in standard $B$-trees. Note that this might cause recursive splits of nodes at greater height.

\vspace{0.15cm}

\noindent \textit{Bounding the insertion cost:} To flush a buffer $I_v$ and move segments to buffers of child nodes $\ensuremath{\mathcal{S}}_{v_i}$ and $I_{v_i}$, we need to perform $O(\ensuremath{B^{\epsilon '}})$ I/Os. Since each segment breaks into at most $\ensuremath{B^{\epsilon '}}$ unit segments, a buffer of size $B$ becomes full after at least $B/ \ensuremath{B^{\epsilon '}} = B^{1-\epsilon'}$ insertions. Thus the amortized cost of moving a segment from a buffer of depth $i$ to depth $i+1$ is $O(\ensuremath{B^{\epsilon '}}/{B^{1-\epsilon'}}) = O(1/B^{1-2\epsilon'})$. Since each segment will be eventually stored in a node of depth $O((1/\epsilon') \cdot \log_B K)$, the amortized cost until it gets inserted is $O(\log_B K/(\epsilon ' \cdot B^{1-2\epsilon'}))$.  The restructuring of $\ensuremath{\mathcal{T}}$ due to splitting full nodes requires amortized $O(1)$ I/Os, as in standard B-trees. Overall insertions require $O(\log_B K/(\epsilon \cdot B^{1-2\epsilon'}) ) = O((\log_B K)/B^{1-\epsilon} ) $ amortized I/Os.

\end{onlyapp}
\end{comment}
\begin{onlymain}

\vspace{0.15cm}

\noindent \textit{Linear space usage:} To avoid increases in space usage due to unit segments, whenever there are $K/\ensuremath{B^{\epsilon '}}$ new segments, we rebuild the whole structure. This way the space usage is $O(K + (K/\ensuremath{B^{\epsilon '}}) \cdot \ensuremath{B^{\epsilon '}}) = O(K)$. This rebuilding requires $O((K/B)\log_B K)$ I/Os, i.e., $ O(\log_B K/B^{1-\epsilon'})$ amortized I/Os, thus it does not asymptotically increase the insertion time.

\end{onlymain}

\paragraph{{\normalfont{\textbf{Deletions.}}}}
The process of deleting a segment, $\sigma$, is similar to insertion: we break $\sigma$ into at most $\ensuremath{B^{\epsilon '}}$ unit segments $\sigma_{\ell},\dotsc,\sigma_r$ where $s_\ell$ and $s_r$ are the leftmost and rightmost slabs spanned by $\sigma$ and apply the deletion procedure for each of those unit segments separately.
\begin{onlymain}
\begin{comment}
To delete a unit segment $\sigma_i$, the deletion procedure and analysis of running time is analogous to the one of the left (right) structure of Section~\ref{sec:left_right} and is deferred to Appendix~\ref{sec:multislab_app}. Consequently we obtain the same bound $O(\log_B K/ B^{1-\epsilon'})$ on the amortized deletion cost. However, since each deletion of a segment translates to at most $\ensuremath{B^{\epsilon '}}$ deletions of unit segments, we get an amortized deletion cost $O(\log_B K/ B^{1-2\epsilon'}) = O(\log_B K/ B^{1-\epsilon})$.
\end{comment}

The deletion algorithm for a unit segment $\sigma_i$ is analogous to the one of the left (right) structure of Section~\ref{sec:left_right}. For completeness we describe it here. To delete a unit segment $\sigma_i$, we first check whether it is stored in the buffers of the root $\ensuremath{\mathcal{S}}_r$ or $I_r$; in this case we delete it. Otherwise, we insert $\sigma_i$ in the deletion buffer of the root $D_r$. Let $v$ be an internal node with children $v_1,\dotsc,v_{\ensuremath{B^{\epsilon '}}}$. Whenever $D_v$ becomes full we flush it and forward the segments to the corresponding children and repeat the same procedure: For a segment $\sigma$ which moves to child $v_i$, we check whether it is stored in $\ensuremath{\mathcal{S}}_{v_i}$ or $I_{v_i}$ and if this is the case, we delete it and update list $L_v$ if necessary. Otherwise, we store $\sigma_i$ in the deletion buffer $D_{v_i}$.

In case segment buffer $\ensuremath{\mathcal{S}}_{v}$ underflows (i.e., $| \ensuremath{\mathcal{S}}_{v} | < B/2 $), we refill it using segments from buffers $\ensuremath{\mathcal{S}}_{v_i}$; segments moved to $\ensuremath{\mathcal{S}}_{v}$ are deleted from $\ensuremath{\mathcal{S}}_{v_i}$ and $L_{v}$ gets updated (if needed). This might cause underflowing segment buffers $\ensuremath{\mathcal{S}}_{v_i}$; we handle those in the same way. In case all buffers $\ensuremath{\mathcal{S}}_{v_i}$ become empty and $| \ensuremath{\mathcal{S}}_{v} | < B$ , we move to $\ensuremath{\mathcal{S}}_{v}$ the segments from $I_v$ until either $| \ensuremath{\mathcal{S}}_{v} | = B$ or $| I_v | = 0$. After $K/\ensuremath{B^{\epsilon '}}$ deletions we rebuild our data structure.

\vspace{0.15cm}
\textit{Remark:} Note that here we split all segments $\sigma$ into unit segments $\sigma_{\ell},\dotsc,\sigma_r$. However, the old segments $\sigma$ are not unit segments and are stored manually in the data structure. However this does not affect our algorithm: whenever the first unit segment $\sigma_i$ which is a part of $\sigma$ reaches the node $v$ such that $\sigma \in \ensuremath{\mathcal{S}}_{v}$, we delete $\sigma$ from $\ensuremath{\mathcal{S}}_v$ and remove $\sigma_i$ from deletion buffers. The remaining segments $\sigma_j$ will eventually reach node $v$ and realize that $\sigma$ is already deleted from $\ensuremath{\mathcal{S}}_v$; at this point $\sigma_j$ gets deleted.

\vspace{0.15cm}
\noindent \textit{Bounding the deletion cost:} The analysis of the deletion cost is identical to the analysis of deletions in the structure of Section~\ref{sec:left_right}. Since each segment breaks into at most $\ensuremath{B^{\epsilon '}}$ unit segments, we get an amortized deletion cost of $O(\log_B K/ B^{1-2\epsilon'}) = O(\log_B K/ B^{1-\epsilon})$.

\vspace{0.15cm}

\noindent \textit{Linear space usage:} Similar to insertions, we need to make sure that the total space used is not increasing asymptotically due to the use of at most $\ensuremath{B^{\epsilon '}}$ unit segments in deletion buffers for each deleted segment $\sigma$. The total capacity of deletion buffers is $O(K)$. Since we rebuild the structure after $K/\ensuremath{B^{\epsilon '}}$ deletions, there are at most $O(K)$ segments stored in deletion buffers, i.e., deletion buffers never get totally full and total space used is $O(K)$

\paragraph{{\normalfont{\textbf{Queries.}}}}
Let $p$ be the query point and $\rho^{+}$ be the the vertical ray emanating from $p$ in the $(+y)$ direction. Let also $s_p$ be the slab containing $p$. We can find $s_p$ in $O(1)$ I/Os\ by storing all slab boundaries in a block. We perform a root-to-leaf search and we keep the first segment $\sigma$ hit by $\rho^{+}$ among segments seen so far. While visiting a node $v$ we do the following: (i) perform a vertical ray-shooting query from $p$ among segments stored in buffers $\ensuremath{\mathcal{S}}_{v}$ and $I_{v}$, and update $\sigma$ if necessary (ii) move to the child $v_i$ which contains the successor segment $t_{p,j}$ of $p$ in list $L_v$ (see Figure~\ref{fig:multislab_query}) and (iii) find in $I_v$ (resp. $D_v$) the segments crossing slab $s_p$ and should be stored (according to the total order) in $\ensuremath{\mathcal{T}}_{v_i}$ and move them to $\ensuremath{\mathcal{S}}_{v_i}$ or $I_{v_i}$ (resp. delete them from $\ensuremath{\mathcal{S}}_{v_i}$ or store it in $D_{v_i}$). If a segment inserted in $D_{v_i}$ is also stored in $I_{v_i}$, we delete it from both buffers.

Once we reach a leaf $v$, we first delete from $\ensuremath{\mathcal{S}}_v$ the segments that are in the deletion buffer of its parent and then we perform ray-shooting query among the segments stored in $\ensuremath{\mathcal{S}}_v$ and update $\sigma$ if necessary.

\textit{Bounding the query cost:} Since we follow a root-to-leaf path, and at each level we need to perform $O(1)$ I/Os, a ray-shooting query for point $p$ is answered in $O((1/\epsilon') \cdot \log_B K) = O(\log_B K)$ I/Os.

\begin{figure}[t]
\centering
\includegraphics[scale= 0.65]{multislab_query.pdf}
\caption{Vertical ray-shooting queries in the multislab structure: Query point $p$ is in slab $s_p$. $\rho$ is the vertical ray emanating from $p$. While being at node $v$ of $\ensuremath{\mathcal{T}}$, to decide in which child to continue our search we examine all minimal segments $t_{p,1}, \dotsc,t_{p,\ensuremath{B^{\epsilon '}}}$ stored in list $L_v$. Among them, the first one hit by $\rho$ is $t_{p,j}$. Thus the search continues at child $v_j$ of $v$.}
\label{fig:multislab_query}
\end{figure}

\end{onlymain}

\section{Counting the Restructuring Cost}
\label{sec:restucture}

In Section~\ref{sec:overview} we proved the Theorem~\ref{thm:main} (query and update bounds of the overall structure) without taking into account the cost of restructuring the interval tree $\ensuremath{\mathcal{I}}$ due to insertions that cause leaves to become full. In this section we show that Theorem~\ref{thm:main} holds while taking into account the restructuring of $\ensuremath{\mathcal{I}}$ as well.

When a leaf becomes full we need to split it. This split in turn might cause the split of the parent and possibly continue up the tree, thus causing some part of the tree $\ensuremath{\mathcal{I}}$ to need rebalancing. While rebalancing, we need to perform updates in the secondary structures so that they are adjusted with the updated nodes of the interval tree $\ensuremath{\mathcal{I}}$. In this section, we show that we can slightly modify our data structure such that all updates in secondary structures can be performed in $O(\frac{\log_B N}{B^{1-\epsilon}})$ amortized I/Os. This implies that Theorem~\ref{thm:main} holds.

\begin{comment}
\gknote{In the next paragraph check whether the amortization argument (last two sentences) holds.}
\end{comment}

\paragraph{{\normalfont{\textbf{Our Approach.}}}} We use a variant of the weight-balanced \ensuremath{B^{\epsilon}}-tree of~\cite{ArgeV03}. Each leaf stores at most $B$ segment endpoints. Let $v$ be a node at height $h-1$ with parent $p(v)$. Node $p(v)$ stores $w_v = \Theta(B \cdot B^{\epsilon h})$ elements in its subtree $\ensuremath{\mathcal{I}}_{p(v)}$. We will show that if node $v$ splits, then we can perform all updates needed in the secondary structures in $O(w_v/B^{1-\epsilon})$ I/Os. This implies that a split requires amortized $O(1/B^{1-\epsilon})$ I/Os, since after a restructuring, there should be at least $\Omega(w_v)$ insertions in $\ensuremath{\mathcal{I}}_{p(v)}$ until the next split is needed. Since each insertion can cause $O(\log_B N)$ splits, we get an amortized restructuring cost of $O(\frac{\log_B N}{B^{1-\epsilon}})$ I/Os\ for insertion.

\paragraph{{\normalfont{\textbf{Splitting a node.}}}} Node $v$ splits into two new nodes $v_1$ and $v_2$. The slab $s_v$ of $v$ is divided into two slabs $s_{v_1},s_{v_2}$ with slab boundary $b$; see Figure~\ref{fig:slabs-split}. To capture this change and update our data structure, we need to perform updates in the secondary structures of $p(v)$ and construct the secondary structures for $v_1,v_2$. We describe these updates in detail and show that they can be performed in $O(w_v/B^{1-\epsilon})$ I/Os. In our analysis we use the fact that all secondary structures (multislab and left/right) storing $K$ segments can be scanned in $O(K/B) $ I/Os.

\begin{figure}[t]
\centering
\includegraphics[scale= 0.6]{split_slabs.pdf}
\caption{Splitting a node $v$ into $v_1$ and $v_2$: slab $s_v$ is divided into slabs $s_{v_1}$ and $s_{v_2}$ with boundary $b$.}
\label{fig:slabs-split}
\end{figure}

\begin{comment}
\gknote{don't have time for formal proof need some B-tree citation.}
\end{comment}

 \paragraph{{\normalfont{\textbf{Updates in secondary structures of $p(v)$.}}}}
 We begin with the construction of left/right structures for $v_1$ and $v_2$ using the previous left/right structures for $v$.  We describe the creation of left structures $L_{v_1}$ and $L_{v_2}$ for $v_1$ and $v_2$, respectively, and the right structures are symmetric. Segments that were stored in $L_v$ and do not cross $b$ (like segment $\sigma_1$ in Figure~\ref{fig:segments-examples}) are stored in $L_{v_2}$; segments of $L_v$ that cross $b$ (see segment $\sigma_2$ in Figure~\ref{fig:segments-examples}) are stored in $L_{v_1}$. To identify if a segment is stored in $L_{v_1}$ or $L_{v_2}$ we just need to scan $L_v$, which takes $O(w_v/B)$ I/Os. Moreover, there are some additional segments that need to be stored in left/right structures of $p(v)$: the segments that are strictly inside the slab of $v$ (i.e. they were stored in secondary structures of $v$) and cross $b$; see e.g. segment $\sigma_3$ in Figure~\ref{fig:segments-examples}. For those segments, their left subsegments are stored in $L_{v_1}$ and their right subsegments in $R_{v_2}$. To find such segments we need to scan all secondary structures stored at $v$. Since each secondary structure can be scanned in $O(w_v/B)$ I/Os\ and there are $O(\ensuremath{B^{\epsilon}})$ structures stored in each node, all this takes $O((w_v/B) \cdot \ensuremath{B^{\epsilon}}) = O(w_v/B^{1-\epsilon})$ I/Os.

 We now proceed to the updates of the multislab structure of $p(v)$. Here, we just need to add some segments to the previous multislab structure. The new segments are the segments of $L_v$ that cross $b$ which are not already stored in the multislab (and symmetrically, the segments of $R_v$ that cross $b$ and are not yet in the multislab). For an example, see segment $\sigma_2$ in Figure~\ref{fig:segments-examples}; before it was not stored in the multislab and now we store its middle subsegment. Note that the middle subsegment is a unit segment (i.e. crosses exactly one slab) thus we don't need to compute a new total order; we can find its position in the total order by comparing it only with segments that cross slab $s_{v_2}$. All those segments that need to be added can be found by scanning $L_v$ and $R_v$ in $O(w_v/B)$ I/Os. Insertions in the multislab of $p(v)$ require $O((\log_B w_v)/B^{1-\epsilon}) = O(w_v/B)$ I/Os. Also, all information stored in nodes of the multislab structure can be updated in $O(w_v/B)$ I/Os. Overall, all updates in the  multislab structure of $v$ are performed in $O(w_v/B)$ I/Os.

\begin{figure}[t]
\centering
\includegraphics[scale= 0.6]{segments_examples.pdf}
\caption{Example of segments that get stored in different secondary structures after a split.  Segment $\sigma_1$ was stored in $L_v$ and, after the split, gets stored in $L_{v_2}$. Segment $\sigma_2$ was stored in $L_v$; following the split its left subsegment is stored in $L_{v_1}$ and its middle subsegment in the multislab structure of $p(v)$. Segment $\sigma_3$ was previously stored in secondary structures of $v$, and after the split it should be stored in structures $L_{v_1}$ and $R_{v_2}$ of $p(v)$. }
\label{fig:segments-examples}
\end{figure}

 \paragraph{{\normalfont{\textbf{Construct secondary structures for $v_1$ and $v_2$.}}}}
 The left and right structures for each child slab of $v_1$ and $v_2$ will be based on the left/right structure of the same slab in $v$ just by removing the segments that cross $b$ (which are assigned to $p(v)$ as we explained above).  Similarly, segments that cross $b$ are excluded from the multislab structure.

  We start with the construction of left/right structures of $v_1$ and $v_2$. We describe the left and the right is symmetric. For each slab $s_k$ of $v$, $1\leq k \leq \ensuremath{B^{\epsilon}}$ we scan the left list $L_k$; the segments that do not cross $b$ remain in $L_k$ and the others are deleted. All this takes $O((w_v/B) \cdot \ensuremath{B^{\epsilon}}) = O(w_v/B^{1-\epsilon}) $ I/Os.

 Finally we create the multislab structures for $v_1$ and $v_2$. Again, we need to scan the multislab of $v$ and delete the segments that cross $b$, which takes $O(w_v/B)$ I/Os. Then we need to build the multislabs of $v_1$ and $v_2$ out of the remaining segments. Since all segments are already sorted according to a total order, this can be done in $O(w_v/B) $ I/Os.

\end{onlymain}
\section{Concluding Remarks}
\label{sec:openprobs}

\begin{onlymain}
We presented the first data structure with sublogarithmic update time for dynamic planar point location in the DAM, matching the update bound achieved by $\ensuremath{B^{\epsilon}}$-trees for the dictionary problem. Moreover, until the very recent work of Munro and Nerich~\cite{MN19} which will appear in SOCG'19, our query bound $O(\log^2_B N)$ was the best known for the problem.  Since in~\cite{MN19} authors achieved the first $o(\log^2_B N)$ query bound, a very interesting research direction is to achieve the ``best of both worlds", i.e. describing a data structure with the query bound of~\cite{MN19} and the update time of the data structure presented in this work.
We conjecture that the optimal bounds for dynamic planar point location in external memory are $O(\log_B N)$ for queries and $O(\log_B N/B^{1-\epsilon})$ (the bound we achieved in this work) for updates.

\end{onlymain}

redpajama_set_name: RedPajamaArXiv


text:
Fists in the Pocket
Fists in the Pocket • 1h 49m
Directed by Marco Bellocchio • 1965 • Italy
Starring Lou Castel, Paola Pitagora, Marino Masé
Tormented by twisted desires, a young man takes drastic measures to rid his grotesquely dysfunctional family of its various afflictions, in this astonishing 1965 debut from Marco Bellocchio. With its coolly assured style, shocking perversity, and savage gallows humor, FISTS IN THE POCKET (I PUGNI IN TASCA) was a gleaming ice pick in the eye of bourgeois family values and Catholic morality, a truly unique work that continues to rank as one of the great achievements of Italian cinema.
Up Next in Fists in the Pocket
FISTS IN THE POCKET: Bernardo Bertolu...
In this video interview, shot in Rome in 2005, acclaimed filmmaker Bernardo Bertolucci (a contemporary of Marco Bellocchio) discusses his reaction to FISTS IN THE POCKET and explains the film's importance to Italian cinema.
A Need for Change
This documentary, made in 2005, features interviews with FISTS IN THE POCKET director Marco Bellocchio, actors Lou Castel and Paola Pitagora, editor Silvano Agosti, and critic Tullio Kezich.

redpajama_set_name: RedPajamaCommonCrawl


Nanocages (NCs) have emerged as a new class of drug-carriers, with a wide range of possibilities in multi-modality medical treatments and theranostics. Nanocages can overcome such limitations as high toxicity caused by anti-cancer chemotherapy or by the nanocarrier itself, due to their unique characteristics. These properties consist of: (1) a high loading-capacity (spacious interior); (2) a porous structure (analogous to openings between the bars of the cage); (3) enabling smart release (a key to unlock the cage); and (4) a low likelihood of unfavorable immune responses (the outside of the cage is safe). In this review, we cover different classes of NC structures such as virus-like particles (VLPs), protein NCs, DNA NCs, supramolecular nanosystems, hybrid metal–organic NCs, gold NCs, carbon-based NCs and silica NCs. Moreover, NC-assisted drug delivery including modification methods, drug immobilization, active targeting, and stimulus-responsive release mechanisms are discussed, highlighting the advantages, disadvantages and challenges. Finally, translation of NCs into clinical applications, and an up-to-date assessment of the nanotoxicology considerations of NCs are presented.


text:
Q: CakePHP 3:Router error, htaccess auto redirect webroot/admin/ When I enter localhost:3000/admin
the url redirects to localhost:3000/webroot/admin
and show error WebrootController not found
But I enter localhost:3000/admin/ is correct
router
Router::prefix('admin', function ($routes) {
    //$routes->connect('/:controller/:action/*', ['prefix' => 'admin']);
    $routes->connect('/', ['controller' => 'admins', 'action' => 'index']);
    $routes->fallbacks('InflectedRoute');
});

htacess:
<IfModule mod_rewrite.c>
    RewriteEngine on
    RewriteRule    ^$ webroot/    [L]
    RewriteRule    (.*) webroot/$1 [L]

My project

A: Remove or change folder name admin in webroot
its may be a cakephp bug.

redpajama_set_name: RedPajamaStackExchange


text:
Harry Potter actress joins new Apple comedy series
Imelda Staunton made our skin crawl as Dolores Umbridge.
Photo: Warner Bros.
Tim Cook's home state might become the backdrop of one of Apple's new TV shows for 2020. Or at least, it's lending its name to it.
In its first comedy co-production with the BBC, Apple has tapped Imelda Staunton to star in a new eight-part series that will also feature Darren Boyd and Phil Davis called Alabama.
Staunton is probably most recognizable to Americans for her role as Dolores Umbridge from the Harry Potter movies. Her credits in the U.K. are very impressive though and she's been nominated for 13 Olivier Awards.
Details on the plot of Alabama are still being kept under wraps. Comedy writer and former stand-up Andy Wolton has signed up to write the show. Production is reportedly underway right now with Castatrophe's Jim O'Hanlon directing and BBC Studio's head of comedy, Chris Sussman, serving as producer.
Alabama likely won't air until sometime in 2020. Apple gave a preview of its upcoming TV shows at an event in March. The first slate of shows is set to come out this fall. It was revealed this morning that one of the most anticipated shows See has a budget that is on par with Game of Thrones.
We'll likely find out more details of Apple's TV service, such as pricing and launch date, at the company's annual fall iPhone event.
Amazon Prime Video app finally adds Chromecast support
Apple TV+ series See reportedly cost nearly $15 million per episode
Developers get their mitts on updated iPadOS 13 and iOS 13 betas
Women and men prefer very different emojis
Wedding photographer's anti-iPhone rant strikes a nerve
Happy World Emoji Day 2019. Here's how to pitch your emoji idea