I/O-efficient dynamic planar point location.
We present an I/O-efficient dynamic data structure for point location in a general planar subdivision. Our structure uses O(<i>N/B</i>) disk blocks of size <i>B</i> to store a subdivision of size <i>N</i>. Queries can be answered in O(log<inf><i>B</i></inf><sup>2</sup><i>N</i>) I/Os in the worst-case, and insertions and deletions can be performed in O(log<inf><i>B</i></inf><sup>2</sup><i>N</i>) and O(log<inf><i>B</i></inf><i>N</i>) I/Os amortized, respectively. Part of our data structure is based on an external version of the so-called logarithmic method that allows for efficient dynamization of static external-memory data structures with certain characteristics. Another important part of our structure is an external data structure for vertical ray-shooting among line segments in the plane with endpoints on <i>B</i> lines, developed using an external version of dynamic fractional cascading. We believe that these methods could prove helpful in the development of other dynamic external memory data structures.
Introduction
Planar point location is dened as follows: Given a planar subdivision  with N vertices (i.e.,
a decomposition of the plane into polygonal regions induced by a straight-line planar graph),
preprocess  into a data structure so that, for an arbitrary query point p, the face of  containing
p can be reported quickly. This problem arises in several applications, including graphics, spatial
databases, and geographic information systems. The planar subdivisions arising in many of these
applications are too massive to t in internal memory and must reside on disk. In such instances,
the I/O communication is the bottleneck instead of the CPU running time. Most of the work to
date, especially if we allow the edges and vertices of  to be changed dynamically, has focused
on minimizing the CPU running time under the assumption that the subdivision ts in main
An extended abstract version of this paper was presented at the sixteenth annual ACM Symposium on Computational
Geometry (SoCG'00).
y Supported in part by National Science Foundation ESS grant EIA{9870734, RI grant EIA-9972879, and CAREER
grant CCR{9984099. Email: large@cs.duke.edu.
z Part of this work was done while visiting Duke University. Email: jan@math.uni-muenster.de.
memory [7, 11, 12, 17, 20, 24]. Only a few results are known for I/O-ecient point location when
the subdivision is stored in external memory [1, 5, 14, 18, 27]. In this paper, we develop the rst
space- and I/O-ecient dynamic data structure for planar point location in general subdivisions.
Previously such a structure was only known for the case of a monotone 1 subdivision [1].
1.1 Previous results
In internal memory, Edelsbrunner et al. [16] proposed an optimal data structure for point location
in monotone subdivisions with O(N) space, O(N) preprocessing time, and O(log 2 N) query time.
For arbitrary planar subdivisions, either the preprocessing time or the space requirement increases
to O(N log 2 N ); see, e.g., [20, 24]. If we allow the edges and vertices to be changed dynamically,
two linear-space structures are known for general subdivisions: one by Cheng and Janardan [11]
that answers queries in O(log 2
supports updates in O(log 2 N) time; the other by
Baumgarten et al. [7] that supports queries in O((log 2 N) log 2 log 2 N) time (worst-case), insertions
in O((log 2 N) log 2 log 2 N) time (amortized), and deletions in O(log 2
structures store the edges of the subdivision in an interval tree [15] constructed on their x-projection
(as rst suggested in [17]) and use this structure to answer vertical ray-shooting queries: for a
query point p, nd the rst edge of  hit by the ray emanating from p in the (+y)-direction. After
answering a vertical ray-shooting query, the face containing p can be found in O(log 2 N) time [23].
A summary of known results can be found in a recent survey [25].
In this paper, we are interested in the problem of dynamically maintaining a planar subdivision
on disk, so that the number of I/O operations (or I/Os) used to perform a query or an update is
minimized. We consider the problem in the standard two-level I/O model proposed by Aggarwal
and Vitter [2]. In this model, N denotes the number of elements in the problem instance, M is the
number of elements tting in internal memory, and B is the number of elements per disk block,
where M < N and 2  B
M . 2 An I/O is the operation of reading (or writing) a disk block
from (or into) external memory. Computations can only be done on elements present in internal
memory. The measures of performance are the number of I/Os used to solve a problem and the
amount of space (disk blocks) used.
Aggarwal and Vitter [2] considered sorting and related problems in the I/O model and proved
that sorting requires ((N=B) log M=B (N=B)) I/Os. Note that under our assumption that B
this is O((N=B) log B N ). Searching a set of N ordered elements requires (log B N) I/Os. I/O-
ecient algorithms and data structures have been developed for numerous problems|see recent
surveys for a sample of these results [3, 28]. Most previous results on point location in external
memory have been either static or batched dynamic: Goodrich et al. [18] designed a static data
structure using O(N=B) space to store a monotone subdivision so that a query can be answered in
optimal O(log B N) I/Os. They also developed a structure for answering a batch of K point-location
queries in optimal O(((N +K)=B) log M=B N) I/Os. Arge et al. [5] extended the batched result to
general subdivisions (see also [14]), and Arge et al. [4] to an o-line dynamic setting in which a
sequence of queries and updates are given in advance and all the queries should be answered as the
sequence of operations is performed. Vahrenhold and Hinrichs [27] considered the problem under
some practical assumptions about the input data. The only known dynamic structure, recently
proposed by Agarwal et al. [1], is restricted to monotone subdivisions. The linear-space (O(N=B)
1 A polygon is called monotone in direction  if any line in direction =2 intersects the polygon in a connected
interval. A planar subdivision  is monotone if all faces of  are monotone in a xed direction.
Sometimes it is only assumed that B < M=2. For simplicity we make the (very realistic) assumption that the
main memory is capable of holding B 2 elements. The techniques developed in this paper all works without this
assumption.
disk blocks) structure supports queries in O(log 2
I/Os in the worst case and updates can be
performed in O(log 2
1.2 Our results
In this paper, we present the rst provably I/O-ecient dynamic data structure for point location
in a general planar subdivision . Our structure uses optimal O(N=B) disk blocks to store .
Queries can be answered in O(log 2
I/Os in the worst-case, and insertions and deletions can be
performed in O(log 2
Part of our data structure is based on a new external version of the so-called logarithmic
method [9] which allows for ecient dynamization of static external-memory data structures with
certain characteristics. More precisely, assume that D is a static external-memory data structure for
an (external order-decomposable [4]) problem P that can be constructed in O((N=B) log B N) I/Os,
such that queries can be answered in O(log kq
I/Os and such that deletions can be performed in
O(log k d
Our method can be used to construct a linear-space
dynamic data structure D 0 for P that answers queries in O(log kq +1
I/Os, and supports
insertions and deletions in O(log 2
Another important part of our structure is a data structure for vertical ray-shooting among
line segments in the plane with endpoints on
lines, developed using a new external
version of dynamic fractional cascading [10, 21]. Direct use of fractional cascading on line segment
data structures is complicated by the fact that not all segments are comparable according to an
above/below relation, i.e., more than one total order can exist on a set of segments in the plane.
We believe that the ideas used in this data structure are of independent interest and that they can
prove helpful in the development of other external memory line segment data structures.
The remainder of this paper is organized as follows; In Section 2 we review the static version of
the structure of Agarwal et al. [1], which works for general subdivisions. We also discuss how this
structure can be modied to support deletions (that is, made semi-dynamic). In Section 3 we then
discuss our general dynamization technique and show how is can be used to obtain a dynamic point
location structure supporting queries in O(log 3
I/Os. In Section 4, we show how to improve
this bound to O(log 2
using an external version of dynamic fractional cascading.
In the following, we will concentrate on answering vertical ray-shooting queries among the edges of
a planar subdivision . As in internal memory, the face containing a query point p can easily be
found in O(log B N) I/Os once the ray-shooting query is answered. To simplify the presentation,
we assume w.l.o.g. that and that vertices in  have distinct x-coordinates

We will make frequent use of (a; b)-trees [19]. In (a; b)-trees, objects are stored in the leaves
which are all on the same level, and all internal nodes (except possibly the root) have between a
and b children. In this paper, a; b 2 (B c ) for some constant 0 < c  1 such that each node can
be stored in O(1) blocks and the tree has height O(log B c normal B-tree [8, 13]
is such a structure with for the case we call the structure a
B-tree. Unless
3 In general, if 2B  M < B 2 , the insertion bound is O(log B N  log M=B (N=B)).
In general a structure that can be constructed in O((N=B) log M=B (N=B)) I/Os, only assuming 2B  M , can be
made dynamic with insertion and deletion bounds O(log B N  log M=B (N=B)) and O(log
specically stated otherwise, we will assume that each leaf contains (B) objects, such that the
tree uses O(N=B) disk blocks in total. Since the tree has height O(log B N ), a search can be
performed in O(log B N) I/Os. Insertion and deletions can also be performed in O(log B N) I/Os
using O(log B N) split and fuse operations on the nodes on a root-leaf path [19].
The basic idea in (the static version of) the structure of Agarwal et al. [1] is similar to the one
used in several main memory structures [7, 11, 17]. The set of edges/segments S of  is stored
in a two-level tree structure, with the rst level being an interval tree|here an external interval
tree [6]|on their x-projection: The base (interval) tree is a
B-tree T over the x-coordinates of
the endpoint of the segments in S. The segments in S are stored in secondary structures associated
with the nodes of T . Each node v of T is associated with a vertical slab s v ; the root is associated
with the whole plane. For each interior node v, s v is partitioned into
vertical slabs s
separated by vertical lines called slab boundaries (the dashed lines in Figure 1 a)), so that each
slab contains the same number of vertices of . Here s i is the slab associated with the i-th child
of v. A segment s of S is stored at the highest node v of T at which it intersects a slab boundary
associated with v. Let S v  S be the set of segments stored at v. A leaf z stores segments whose
endpoints both lie in the interior of the slab s z . The number of segments stored in a leaf is O(B),
hence, they occupy O(1) blocks.
Let v be an internal node of T , let s be a segment of S v , and suppose that the left endpoint
of s lies in the slab s l and that the right endpoint of s lies in the slab s r associated with v. We call
the subsegment s \ s l the left subsegment of s, s \ s r the right subsegment, and the portion of s
lying in s is called the middle subsegment|see also Figure 1 a). Let R denote the set
of middle subsegments of segments in S v . For each 1  i
B, let L i denote the set of
left (resp., right) subsegments that lie in s i . We store the following secondary structures at v.
(i) A multislab structure M on the set of middle segments R.
(ii) For each 1  i
B, we have the following structures:
{ A left structure  i on all segments of L
{ A right structure i on all segments of R i .
A segment in S v is thus stored in at most three secondary structures: the multislab structure,
a left structure, and a right structure. For example, the segment s in Figure 1 a) is stored in
the multislab structure M, the left structure  1 of s 1 , and in the right structure 4 of s 4 . The
secondary structures are constructed to use linear space so each node v requires O(jS v j=B) disk
blocks, which in turn means that overall the data structure requires O(N=B) disk blocks.
s
s
s
s
a)
R

Figure

1: a) A node in the base tree T . The left subsegment of s is in slab s 1 , the right subsegment
in slab s 4 , and the middle subsegment of s spans s 2 and s 3 . b) Answering a query.
be the ray emanating from a point p in the (+y)-direction. To nd the rst segment
of S hit by  + , we search T along a path of length O(log B N) from the root to a leaf z, such that s z
contains p. At each internal node v visited by the query procedure, we compute the rst segment
of S v hit by  + . In particular, we rst search M to nd the rst segment of R hit by  + . Next,
we nd the vertical slab s i that contains p and search  i and i to nd the rst segments of L i
and R i , respectively, hit by  + |refer to Figure 1 b). The rst segment of S z hit by  + is computed
by testing all segments of S z explicitly. The query is then answered by choosing the lowest segment
among the O(log B N) segments found this way.
Based on ideas due to Cheng and Jarnadan [11], Agarwal et al. [1] showed how the left and
right structures  i and i can be implemented eciently.
Lemma 1 (Agarwal et al. [1]) A set of K disjoint segments all of whose right (left) endpoints
lie on a single vertical line can be stored in a data structure using O(K=B) blocks, so that a vertical
ray-shooting query can be answered in O(log B K) I/Os. Updates can be performed in O(log B K)
I/Os. The structure can be constructed in O((K=B) log B K) I/Os.
Agarwal et al. [1] also showed how the multislab structure can be implemented such that queries
can be answered in O(log B N) I/Os. While the left and right structures support general updates,
Agarwal et al. [1] only managed to make the multislab structure dynamic for monotone subdivisions.
Below we discuss this structure further and show how it can easily be modied to support deletions
for general subdivisions.
set of K disjoint segments with endpoints on
vertical lines can be stored in
a data structure M using O(K=B) blocks, so that a vertical ray-shooting query can be answered
in O(log B K) I/Os. A deletion can be performed in O(log B K) I/Os and the structure can be
constructed in O((K=B) log B K) I/Os.
Lemma 1 and 2 implies that the structure by Agarwal et al. [1] can answer a query in
I/Os. The structure can be constructed in O((N=B) log B N) I/Os; First the base
tree T is constructed by sorting the endpoints of the segments S using O((N=B) log M=B
O((N=B) log B N) I/Os, and then building the tree bottom-up using an additional O(N=B) I/Os.
Next the segments in S are sorted by the left x-coordinate and distributed to the internal nodes in
O((N=B) log B N) I/Os by visiting the nodes of T level-by-level while scanning the sorted list on
each level. Finally, the secondary structures of all nodes are constructed in O((N=B) log B N) I/Os
in total (Lemma 1 and 2). Using the O((N=B) log B N) I/O construction algorithm, deletions can
also be supported. To delete a segment s we search down T until we nd the node v where s is
stored. Since both the multislab structure M and the left and right structures  i and i support
deletions in O(log B N) I/Os (Lemma 1 and 2), we can then delete s in O(log B N) I/Os. Finally,
we use global rebuilding [22] to maintain the O(log B N) height of the base tree T , that is, delete
the endpoints of s from the leaves and rebalance T ; Since the space and query performance remain
asymptotically the same as long as o(N) deletes have been performed we do not need to rebalance
immediately. Instead we simply rebuild the structure after N=2 updates using O((N=B) log B N)
I/Os, or O((log B N)=B) I/Os amortized per delete. Thus we have the following.
Theorem 1 A set S of N disjoint segments can be stored in a data structure using O(N=B)
disk blocks, so that a vertical ray-shooting query can be answered in O(log 2
I/Os, and such
that deletes can be performed in O(log B N) I/Os amortized. The structure can be constructed in
I/Os.
We now describe the multislab structure designed in [1] in further detail, that is, prove Lemma 2.
In order to do so we need to dene a partial order  on non-intersecting segments.
Denition 1 A segment s in the plane is above a segment t in the plane, t  s, if there exists
a vertical line l intersecting both s and t such that the intersection between l and s is above the
intersection between l and t.
Note that two segments are incomparable if they cannot be intersected by the same vertical
line. The segment sorting problem is the problem of extending the partial order  to a total order.
Lemma 3 (Arge et al. [5]) A set of N disjoint segments can be sorted according to the partial
order  in O((N=B) log M=B I/Os.
Consider a set R of K disjoint segments whose endpoints lie on
vertical lines b
B+1 .
For
B, let s i be the vertical slab bounded by b i and b i+1 . If R, and hence also the subset
R 0 of R crossing s i , is sorted according to , we can easily answer a ray-shooting query in O(log B N)
I/Os using a B-tree on R 0 . However, we cannot aord to build a B-tree on the segments crossing
each slab, since this could result in each segment being stored
times. Therefore the segments
are stored in a single multislab structure M as follows: First a
B-tree is constructed on the
sorted sequence of segments in R. For a node v 2 , let R v denote the subsequence of R stored
in the subtree rooted at v. To guide processing of queries, certain segments of R v are stored at
each internal node v of . More specically, let w
B denote the children of an internal
node v. For 1
B, we dene  ij to be the maximal segment of Rw i (according to ) that
intersects the vertical slab s j . If no segment of Rw i intersects s j ,  ij is undened. All less than
are stored at v in O(1) blocks. Note that a segment s is stored on at most one
root-leaf path. The
B-tree requires O(K=B) disk blocks and can be constructed (bottom-up)
in O(K=B) I/Os, assuming that R v is sorted according to the  ordering.
To nd the rst segment hit by a query ray  + , we follow a path from the root to a leaf z of
so that R z contains the rst segment hit by  At each node v visited by the procedure we do
the following. If p lies in the interior of slab s r , let
Bg. The denition of  ij
ensures that, if  lr is the rst (lowest) segment of E v hit by  contains the rst segment
of R hit by  + . We therefore visit w l next. In total, a query can be answered in O(log B N) I/Os.
One way of thinking of is as a
B-tree for each of the
B slabs, all stored in the same structure;
When answering a query in slab s r , the sets E v of all nodes v in denes a
B-tree on segments
intersecting s r .
The main problem in making dynamic is that insertion of a new segment may change the
total order of the segments in R considerably. In [1] special features of monotone subdivisions [26]
are used to limit such changes. Deletion of a segment t, on the other hand, does not change the
sorted sequence of segments in R is still a sorted sequence after deleting t. This makes
it easy to perform deletions eciently. To delete t stored in leaf z, we rst nd for each of the
at most
crossed by t, the maximal segment t j in z below t. Then we delete t in z
and traverse the path from z to the root, exchanging each  with the relevant segment t j
it to be in the rst node
encountered where some  ij is dened). This requires O(log B N) I/Os. The deletions may result
in leaves storing o(B) segments but the space and query performance remain asymptotically the
same as long as o(N) deletes have been performed. After N=2 deletes we can simply rebuild the
structure using O((N=B) log B N) I/Os, or O((log B N)=B) I/Os amortized per delete. This proves
Lemma 2.
3 Dynamization using the logarithmic method
In this section, we discuss a general method for transforming a static external-memory data structure
with certain characteristics into an ecient dynamic structure. The method is an external
version of the logarithmic method [9] (see also [22]). We also discuss how the method can be used
to make the semidynamic point location structure described in the previous section fully dynamic.
The logarithmic method works for a (broad) class of so-called decomposable searching problems
rst dened by Bentley [9] and previously considered in an external setting by Arge et al. [4].
Denition 2 (Arge et al. [4]) Let P be a searching problem and let P(x; V ) denote the answer
to P with respect to a set of objects V and a query x. P is called external-decomposable, if for any
partition A[B of V and for any query x, P(x; V ) can be computed in O(1) additional I/Os given
P(x; in appropriate form.
The vertical ray shooting problem is external-decomposable, in fact, we already used this in
Section 2 where we solved the problem by solving it on O(log B N) disjoint segment subsets and
returning the appropriate segment. Bentley [9] described a general method for making static data
structures for decomposable problems dynamic. The main idea is to partition the set of objects V
into log 2 N subsets V i of exponentially increasing size 2 i and build a static structure D i for each of
these subsets. Queries are then performed by querying each D i and combining the answers, while
insertions are performed by nding the rst empty D i , discarding all structures D j , j < i, and
building D i from the new object and the objects in V j , j < i.
To make the logarithmic method I/O-ecient, we need to decrease the number of subsets to
log B N , which in turn means increasing the size of V i to B i . However, when doing so
do not contain enough objects to build D i . It turns out that if we can build a static structure
I/O-eciently enough we can resolve this problem and make a modied version of the method
work in external memory: Consider a static structure D for an external-decomposable problem P
that can be constructed on a set V of N objects in O((N=B) log M=B N) I/Os and answers queries
in O(log kq
I/Os. Also assume that D supports deletions in O(log k d
I/Os. We partition V
into log B N sets V i , such that jV i construct an external memory static data structure
D i for each V i |refer to Figure 2. To answer a query, we simply query each D i and combine the
results using O(
log kq
I/Os.
An insertion is handled by nding the rst structure D i such that
discarding
all structures D j , j  i, and building a new D i from the objects in these structures using
I/Os. Now because of the way D i was chosen,
we know that
which means that at least B i 1 objects are moved from lower indexed
structures D j to D i . If we divide the D i construction cost between these object, each of themV < B < BV 2

Figure

2: Logarithmic method: Structure D i contains jV objects. Note that D 1 ; D
do not contain enough objects to build a D j+1 of size B j+1 .
has to pay O(log M=B (N=B)) I/Os. Since an object never moves from a higher to a lower indexed
structure, we can at most charge it O(log B N) times during N insertions. Thus the amortized cost
of an insertion is O(log B N  log M=B (N=B)) I/Os. Note that the key to making the method work is
that the factor of B we lost when charging the construction of a structure of size B i to only
objects is oset by the B factor we win in the construction bound.
In order to support deletions eciently, we maintain a separate B-tree C on the objects V . With
each object in C we store information about which structure D i contains the object. Note that this
adds an extra O(log 2
I/Os to the insertion bound, since we need to update the entries in C of
all the O(B objects that moves from D j to D i , j < i, during an insertion. To delete a given
object we rst use C to determine the structure D i storing the object in O(log B N) I/Os. Once
D i is found, we can perform the deletion in O(log k d
I/Os. Finally, in order to guarantee that
the number of structures D i remains O(log B N ), we also perform a global rebuilding [22] of the
structure once half of the objects have been deleted, that is, we collect all O(N) objects, discard all
data structures D i , and build a new D log B N structure using O((N=B) log M=B (N=B)) I/Os. This
adds O((1=B) log M=B I/Os amortized to the deletion cost.
Theorem 2 Let P be an external-decomposable problem on a set V of size N . Let D be a linear-space
static structure for P which can be constructed in O((N=B) log M=B (N=B)) I/Os, such that
queries can be answered in O(log kq
I/Os and such that deletes can be performed in O(log k d
I/Os
There exists a linear-space dynamic data structure D 0 for P that answers queries in O(log kq +1
I/Os, and supports insertions and deletions in O(log B N  log M=B (N=B)) and O(log
I/Os amortized, respectively.
Note that we did not use the M > B 2 assumption in the proof of Theorem 2, that is, the
Theorem holds if just M > 2B. It is easy to see that if M > B 2 and the static structure can
be constructed in O((N=B) log B N) I/Os the insertion bound becomes O(log 2
using the
method on the semi-dynamic structure described in Section 2 (Theorem 1), we immediately obtain
the following.
Theorem 3 A set S of N disjoint segments can be stored in a data structure using O(N=B) disk
blocks, such that a vertical ray-shooting query can be answered in O(log 3
I/Os, and such that
insertions and deletions can be performed in O(log 2
B N) and O(log B N) I/Os amortized, respectively.
Improved dynamic structure
In the previous section, we obtained a structure for answering vertical ray-shooting queries in
O(log 3
by using the logarithmic method on the full semi-dynamic structure of Section 2.
The same result could also have been obtained in an alternative way; To insert a segment s in the
structure of Section 2, we search down the base tree T in O(log B N) I/Os until we nd the node v
where s should be stored. Since the left and right structures already support insertions, almost the
only thing we need to consider is how to insert a segment s in a multislab structure M. We also
need to consider how to insert the endpoints of s in the base tree T . Agarwal et al. [1] showed that
using weight-balanced B-trees [6], an insertion of an endpoint in the base tree can be handled in
amortized. This means that by applying the logarithmic method to the multislab
structure (Lemma 2), obtaining a O(log 2
query and insertion structure, we again obtain the
result of Theorem 3. In this section, we show how to design a modied multislab structure such
that a query can be answered in O(log B N) I/Os, leading to an improved overall O(log 2
query
bound.
Consider a multislab structure storing a set R of N disjoint segments whose endpoints lie on
B+1 . As previously, let s
B, be the vertical slab bounded
by b i and b i+1 . Like in the logarithmic method, we will divide R into log B N disjoint subsets R i
of size less than N and store R i in a data structure D i . The main idea we will use to obtain
an O(log B N) query bound is similar to fractional cascading [10]. We will iteratively (starting at
with a set B i of segments sampled from D i+1 , and use these segments
to avoid the O(log B N) I/O cost of searching in D i+1 when answering a query.
Since two segments in the plane are not always comparable (Denition 1), fractional cascading
is not directly applicable to our problem. Normally when applying fractional cascading, we would
sample uniformly from the sorted sequence of segments in R i+1 . Intuitively, knowing the rst
segment b in B i hit by a vertical ray  should then make it possible to nd the rst segment
r in R i+1 hit by  eciently, because not too many segments could be between b and r in the
sorted sequence of segments in R i+1 . Unfortunately, this is not the case, since many segments
incomparable with b and r could be between the two segments in the sorted order. This problem
arises even if we sample segments uniformly in each slab s j . In the following we show how to
overcome these problems by indeed sampling segments uniformly in each slab, but additionally
designing D i+1 such that the segments in R i+1 between two known sampled segments l 1 and l 2 in
s j can be searched eciently (in O(1) I/Os). A key to obtaining this result is to store all segments
between l 1 and l 2 crossing s j together in a secondary structure. One complication is that a segment
can cross many slabs and we have to be careful not to store each segment in too many secondary
structures, as doing so would make deletion of a segment inecient.
To help the exposition, we will in the following refer to the original segments R i as red segments
and to the segments B i sampled in D i+1 and stored in D i as blue segments. We also refer to the
original segments from B i in D i+1 as green segments G i+1 . A blue segment in B i stores a pointer
to the corresponding green segment in G i+1 . The rest of this section is organized as follows. In
Section 4.1 we rst discuss how to sample the segments B i so that jR In
Section 4.2 we describe D i and show how it can be constructed using
linear space given R i In Section 4.3 we show how to answer a vertical ray shooting
query in O(log B N) I/Os overall, and in Section 4.4 we discuss how to perform insertions and
deletions in O(log 2
B N) and O(log B N) I/Os, respectively. Thus we obtain the following.
Lemma 4 A set R of N disjoint segments with endpoints on
vertical lines can be stored in
a data structure D using O(N=B) blocks, so that a vertical ray-shooting query can be answered in
I/Os. Segments can be inserted or deleted in O(log 2
respectively, and D can be constructed in O((N=B) log B N) I/Os.
As discussed above, this leads to our main result.
Theorem 4 There exists a data structure using O(N=B) blocks to store a planar subdivision of
size N , such that a vertical ray-shooting query can be answered in O(log 2
worst case and
such that insertions and deletions can be performed in O(log 2
respectively.
4.1 Sampling segments
Given k (k  log B N) disjoint sets R 1 red segments such that jR i j  N
sample the blue B i (green G i+1 ) segments iteratively (starting with
the sorted sequence of segments in R be the (sorted sequence of) segments
from V crossing slab s j . Consider constructing a set of segments G s j in slab s j by sampling every
)'th segment from V s j and cutting sampled segments to slab boundaries (that is, if a
segment t is sampled from V s j the subsegment t \ s j is inserted in G s j ). The set of green segments
G i+1 sampled from R i+1 consists of all such sampled segments G s 1
. We say that
two segments are consecutive in s j (or that g 2 is the successor of g 1 in s j ), if they
are consecutive in the sorted list of segments in G s j . When building D i+1 on R i+1 and B i+1 we
will also include the segments in G i+1 . B i now consists of copies of the segments in G i+1 , where
each segment is augmented with a pointer to the identical segment in G i+1 . Since we sample every
segment in each of the
slabs, we can inductively prove that the size of B i (and
bounded by
thus that jR
Given the red and blue segment sets R i and B i , the green and blue segments G i and B i 1 can
easily be computed I/O-eciently as follows, starting with rst compute
by sorting the segments in R i using the algorithm by Arge et al. [5]. This is done using
scanning
through V and collect the segments in G s j for all slabs s j (while \cutting" them to slab boundaries);
We simply maintain a counter for each of the
counting how many segments spanning a
given slab we have encountered, and output the relevant segments to a (sorted) list. In total we use
sample segments from R i and B i , so overall we use O((N k =B) log B N k )
I/Os to construct all blue and green segment sets B i and G i .
Lemma 5 Given red segments R 1 of blue and green
segments can be constructed in O((N k =B) log B N k ) I/Os.
4.2 Constructing D i
We now describe the structure D i build on the segments in R . Note that when we
later describe how to delete a segment s, we will only delete the original red segment s and not
the blue or green segments possibly produced from s. This means that the number of red segments
between green segments sampled in the same slab can become much smaller than the originalp
segments.
The structure D i consists of
structures: The main structure M i on the red, blue and
green segments R sample structure U ij on the green segments from G i in s j for
each of the
. The main structure M i is a two-level structure. The base structure is
a
B-ary tree over the sorted sequence of segments in R i with each leaf containing B 3
segments. Segments are also stored in secondary structures of each internal node of : For each
each pair of consecutive green segments the less than 2
segments
in crossing slab s j between g 1 and g 2 are stored in the minimal common ancestor v of the
leaves containing g 1 and segment s is assigned to v several times, only
one copy is actually stored. g 1 and g 2 also store pointers to v, and each (copy of a) segment s in a
secondary structure contains a pointer to the leaf storing s. Finally, with each green segment in s j
we also store the minimal (rst) blue segment above it crossing s j .
The number of segments stored in each internal node v of is bounded by O(B 3
segments are stored at v for at most
of consecutive green segments; For
each of the
a pair of consecutive green segments in s j storing segments at v have to be
stored below dierent, of the
B, children of v. As the number of internal nodes is O(N i =(B 3
B),
the total number of segments stored in secondary structures is O(B 3
Each node v (internal or leaf) of has two secondary structures, R v and B v , storing red and blue
segments, respectively. Both structures are implemented as the multislab structure of Section 2.
Using Lemma 2, this means that they use linear space, and that vertical ray-shooting queries can
be answered and deletions performed on them in O(log B (2B 3
I/Os. In addition to
R v and B v , v also contains an index block I v containing information about how many red segments
are stored in v for each of the at most
of green segments storing segments in v.
Given the segments in R i , B i , and G i in sorted order, M i can be constructed I/O-eciently as
follows: First is constructed using O(N i =B) I/Os in a level-by-level bottom-up manner. Next
the segments in the leaves of are scanned in sorted order and MCA(g computed for each
consecutive pair of green segments in a slab. We maintain the last encountered green segment in each
slab and compute the relevant minimal common ancestor by searching up the tree using O(log B
I/Os when encountering a new green segment. At the same time we also compute the minimal blue
segment directly above each green segment. In total we use O(jG
I/Os. Next we scan through the leaves again, constructing a list of red and blue segments marked
with the internal node they need to be stored in. Note that as mentioned earlier, only one copy
of a given segment is assigned to each node. Then we sort this list in O((N=B) log M=B
I/Os to obtain for each node v the segments to be stored in R v and B v . Finally,
R v and B v (as well as I v ) are constructed in a O((B 3
for each node v (Lemma 2), or O(N i =B) I/Os in total. Thus we use O((N i =B) log B N i ) I/Os to
construct M i .
. Consider two consecutive segments to
be non-redundant if R i contains at least one red segment crossing s j between g 1 and g 2 . We dene
the lowest non-redundant segment of a green segment g in s j to be the lowest non-redundant green
segment in s j above g (note that it can be g itself). The lowest non-redundant segments naturally
partition the sorted sequence of green segments in s j , and thus also the sorted sequence of their
endpoints on one of the boundaries of s j |refer to Figure 3 a). Deletion of a red segment in R i
may result in two such partitions merging.
s
Non-redundant
Non-redundant
a)
Find(
s

Figure

3: a) Six green segments in a slab s j and three red segments crossing s j . Two of the green
segments are non-redundant and the partition of the segments (endpoints) induced by the lowest
non-redundant segment relationships are indicated on the rightmost endpoints. b) Finding the red
segment immediately above p given the green segment g i+1 immediately above p. RMCA(g 0 ;g
and RMCA(g 00 ;g 000 ) are queried.
A sample structure U ij maintains the lowest non-redundant segment for each green segment
implemented using an interval Union-Find structure such that Find(g) returns
the lowest non-redundant segment of g, and such that Union(g) merges the partition containing
g with the partition above this partition (i.e., with the partition containing the successor g 0 2 G i
of Find(g) in s j ). In Section 4.5 we show how an interval Union-Find structure on K elements
can be implemented such that it can be initialized using O(K log B K) I/O and such that Union
operations are free (amortized), while Find operations take O(1) I/Os. We can construct all the
sample structures U ij in O((N i =B) log B N i ) I/Os as follows; We rst produce a list of the green
segments in G i with all non-redundant segments marked. We do so by scanning through the list
of sorted segments in R i collecting the green segments while in main memory keeping
track of the last green segment seen in each of the
B. When processing a red segment r we
then simply mark all green segments in each slab crossed by r. After the scan, the sorted list
of green segments for each slab s j is produced in O((N=B) log M=B
I/Os by sorting the list. Finally, we produce U ij for each slab s j in turn by rst initializing an
interval Union-Find structure on the green segments in s j and then performing a Union operation
corresponding to each redundant segment. As the number of green segments is O(N i =B), this takes
Lemma 6 Given R in sorted order, D i can be constructed in O((N i =B) log B N i ) I/Os.
4.3 Answering a vertical ray-shooting query
Consider a query p in slab s j . To nd the rst segment hit by a ray  + emanating from p, we rst
load D 1 into main-memory and determine the rst red segment r 1 2 R 1 and the rst blue segment
We then repeatedly use the pointer from the blue segment b i in D i to the green
segment g i+1 in D i+1 to compute the rst segments r
To compute the blue segment b i+1 , we consider the green segment g 0 in s j immediately below g i+1 ,
and query BMCA(g 0 ;g i+1 ) in M i for the rst blue segment hit by  + . If no such segment exists,
we return the minimal blue segment above g i+1 stored with g i+1 . Similarly, to compute the red
segment r i+1 , we rst query RMCA(g 0 ;g i+1 ) . If no red segment is found, we perform a Find(g i+1 ) on
U ij to determine the lowest non-redundant green segment g 00 in s j . Querying RMCA(g 00 ;g 000 ) , where
000 is the successor of g 00 in s j , we then obtain r i+1 . Refer to Figure 3 b).
As the above query procedure spends O(1) I/Os in each D i , it uses O(log B N) I/Os in total. As
ray-shooting is external-decomposable, we can easily answer the query in another O(log B N) I/Os
once r i , 1  i  log B N , have been found.
Lemma 7 A vertical ray-shooting query among N segments in D i , 1  i  log B N , can be answered
in O(log B N) I/Os.
4.4 Performing updates
An insertion is basically handled as in the general logarithmic method. We nd the rst structure
D i such that
build a new D i from the red
segments R j in these structures and the blue segments B i using O((N i
Unlike in the logarithmic method, we also need to rebuild the structures D j , j < i, starting with
segment sets R . We do so in O(
I/Os by rst producing the sampled segments B j , j < i, as discussed in Section 4.1 (Lemma 5), and
then building D j , j < i, as discussed in Section 4.2 (Lemma 6). As previously, we can argue that at
least red segments are moved from lower index structures D j to D i , and charging the
rebuilding cost to these segments we obtain an O(log 2
amortized insertion
bound.
A deletion of a segment s is handled as follows: We rst determine the structure D i , as well
as the leaf l of the main structure M i of D i , containing s. Next we delete s from Rw of all nodes
w on the path from the root of M i to l. Because of the way segments were assigned to secondary
structures, s cannot be stored in any other secondary structure. When deleting s from Rw we also
decrement the relevant counters in I w (counting the number of red segments between each pair
of consecutive green segments storing segments in w), and using these counters we determine if
any of the green segments in G i become redundant as a result of the deletion. If a green segment
becomes redundant, we perform a Union(g) on the relevant sample structure U ij . As in the
logarithmic method, we also perform a global rebuilding once half of the original segments have
been deleted.
The relevant structure D i and leaf l can be located in O(log B N) I/Os by querying with one of
the endpoints of s (or using a separate B-tree as discussed in Section 3). Deleting s from Rw and
updating I w in the O(log B N) nodes w on the path from l to the root of M i is also performed in
O(log B N) I/Os in total. As discussed earlier, we charge the cost of all Union operations to the
construction of D i (note however, that in the worst case we perform
log B N such operations).
Finally, the global rebuilding adds another O(log B N) I/Os amortized to the deletion cost.
insertions and deletions in O(log 2
amortized, respectively.
4.5 I/O-ecient interval Union-Find structure
Consider K ordered elements Initially, all x i are considered singleton
sets and Find(x i Union operations are used to join neighboring sets [x
and a Find should return the maximal element in a set of consecutive elements. More
formally, if x j is in the set [x joins the set of
elements x l with Find(x l and the set of elements xm with Find(xm
Find(x q ) > Find(x j )g.
An interval Union-Find structure can be implemented I/O-eciently in a straightforward way
using height one trees. We initially store the N elements consecutively on disk with each element
containing a pointer to a root containing a copy of element Find(x i We maintain that
all elements x i point to Find such that a Find operation can be performed in O(1) I/Os. The
root elements are stored consecutively on disk such that the structure occupies O(N=B) blocks.
A Union operation is implemented such that when combining two consecutive sets of elements
we update all elements of S 2 to point to the root of S 1 , that is, we
update the pointers of the smallest set. As elements are stored consecutively on disk this can
be accomplished in O(1 I/Os. As the root pointer of each element can be changed at
most log 2 N times, the overall cost of U Union operations is bounded by O(U
I/Os. As U < N we obtain the following.
Lemma 9 An interval Union-Find structure on N elements can be implemented using O(N=B)
disk blocks such that Find is performed in O(1) I/Os and such that U Union operations are performed
in O(N log B N) I/Os in total.
5 Conclusions and open problems
In this paper, we presented a linear space and I/O-ecient dynamic data structure for point location
in a general planar subdivision. Important parts of our data structure are based on a new external
version of the logarithmic method [9], as well as a new external version of dynamic fractional
cascading [10, 21].
Several challenging problems remains open. One example is if the query and/or insertion bounds
can be improved to O(log B N ). Note that such an improvement would also lead to an improved
internal memory structure. Another example is to develop higher-dimensional structures.

Acknowledgments

The rst author would like to thank Pankaj Agarwal for many inspiring point location discussions.



--R


The Input/Output complexity of sorting and related problems.
External memory data structures.
Theory and practice of I/O- ecient algorithms for multidimensional batched searching problems

Optimal dynamic interval management in external memory.
Dynamic point location in general subdivisions.
Organization and maintenance of large ordered indexes.
Decomposable searching problems.
Fractional cascading: I.
New results on dynamic planar point location.

The ubiquitous B-tree
Randomized external-memory algorithms for some geometric problems
A new approach to rectangle intersections

A space-optimal solution of general region location

A new data structure for representing sorted lists.
Optimal search in planar subdivisions.

The Design of Dynamic Data Structures.
Range searching in a set of line segments.
Planar point location using persistent search trees.
Point location.
Dynamic maintenance of planar digraphs
Planar point location for large data sets: To seek or not to seek.
External memory algorithms and data structures: Dealing with MASSIVE data.
--TR
Planar point location using persistent search trees
Optimal point location in a monotone subdivision
The input/output complexity of sorting and related problems
New results on dynamic planar point location
Dynamic point location in general subdivisions
A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps
Point location
I/O-efficient dynamic point location in monotone planar subdivisions
Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems
Range searching in a set of line segments
Ubiquitous B-Tree
External memory algorithms and data structures
Design of Dynamic Data Structures
External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract)
External memory data structures
Planar point location for large data sets
Optimal External Memory Interval Management

--CTR
Lars Arge , Mark de Berg , Herman J. Haverkort , Ke Yi, The Priority R-tree: a practically efficient and worst-case optimal R-tree, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Pankaj K. Agarwal , Lars Arge , Ke Yi, An optimal dynamic interval stabbing-max data structure?, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Lars Arge , Mark de Berg , Herman Haverkort, Cache-oblivious R-trees, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
dynamic data structures;external memory;point location;I/O efficient