数理解析研究所講究録
第 534 巻 1984 年 247-261$2_{-}47$

Dynamic Orthogonal Segment Intersection Search and Its Applications

Hiroshi IMAI and Takao ASANO
Department of Mathematical Engineering and Instrumentation Physics,
Faculty of Engineering, University of Tokyo, Bunkyo-ku, Tokyo 113, Japan

Abstract
This paper develops data structures for maintaining a set of orthogonal segments,
where a segment in the plane is called orthogonal if it is horizontal or vertical. By
combining the data structures with graph algorithms for depth-first search, matchings,
etc., or with algorithms in computational geometry, we obtain algorithms, with better
time complexities, for problems on orthogonal segments, which arise in various fields
such as VLSI design, computer graphics and database system.

1. Introduction

The orthogonal segment intersection search problem is stated as follows: Given a setof orthogonal segments in the plane, report all the segments in that intersect agiven orthog\’onal query segment. Here a segment in the plane is called orthogonal if it
is horizontal or vertical. The problem is called static if the set remains unchanged,
is updated by insertions or deletions. Until now, efficientand dynamic if the set
data structures for this problem have been developed [1,2,3,16,18,23]. For the static
problem, Chazelle’s $0(\log n+k)$ -time and $O(n)$ -space algorithm is the best known
solution [21, where is the number of reported intersections. For the dynamic problem in which the size of the underlying set in the course of the algorithm is known to
be $O(n)$ in advance, McCreight [181 showed an algorithm with $O((\log n)^{2}+k)$ query
time, $0((\log n)^{2})$ update time and $0(n)$ space, and Lipski and Papadimitriou [161presented an algorithm with ( $\log n$ log log $n+k$ ) query time, ( $\log n$ log log n) update
time and $O(n\log n)$ space. For the general dynamic problem, Edelsbrunner [31 gavean algorithm with $O((\log n)^{2}+k)$ query time, $O((\log n)^{2})$ update time and $0(n\log n)$
space.
In this paper, we consider two restricted types of dynamic orthogonal segmentintersection search problems. One is called an insertion problem in which the underlying set of orthogonal segments is updated only by insertions. The other is called adeletion problem in which the set is updated only by deletions. We show that, in bothproblems, an intermixed sequence of $O(n)$ queries and updates can be executed online in $0(n\log n+K)$ time and $O(n\log n)$ space, where $K$ is the total number ofreported intersections. That is, each of queries and updates in both problems can be
executed in $O(\log n(+k))$ time in an amortized sense. Our data structure is a combination of the layered segment tree developed by Vaishnavi and Wood [231, which was
$S$

$S$

$n$

$S$

$S$

$k$

$O$

$O$

-1-

$2\backslash \delta_{\triangleleft}^{Q}\mathfrak{B}\vee$originally designed for the static problem, and linear-time set-union and set-splitting
algorithms due to Gabow and Tarjan [51. Here, in order to obtain the result for theinsertion problem described above, we must generalize Gabow and Tarjan’s setsplitting algorithm in such a way that the ground set can be incremented, which is themain problem discussed in section 2. In section 3, we discuss about dynamic layered
segment trees, and show the main theorems for the insertion and deletion problems.
By combining the data structures with graph algorithms or with algorithms in computational geometry, we obtain various new results for problems on orthogonal segments, which arise in many fields. A basic idea combining the data structure for thedeletion problem with graph algorithms such as depth-first search and breadth-firstsearch was found in Lipski [13]. Imai and Asano [7] independently obtained a similaridea, and developed the idea further in [9]. Here, from the more general point ofview, as applications of both insertion and deletion problems, we discuss, in section 4,
seven problems the time complexities of which are improved by means of the data
structures developed in this paper.

2. Set-Union and Set-Splitting Problems. Suppose thatbe such thatandare dummy elements.
and $0\equiv s_{0}<s_{1}<\cdots<s_{p}<s_{p+1}\equiv n+1$ , where
Define $V(s_{i})(i=1,\ldots,p+1)$ to be $\{u|u\in U,s_{i-1}<u\leq s_{i}\}$ . Then $\{V(s_{f})|i=1,\ldots,p+1\}$ issuch that $1\leq i<j\leq p+1$ , wea partition of , and, for any
and. We call $(V(s_{1}),\ldots, V(s_{p+1}))$ an ordered partition of with respect to , andhave
is called the ground set of the ordered partition
denote it by $P(U,S)$ . The set$P(U,S)$ .
For the ordered partition $P(U,S)$ , we consider the following four operations, find,link, split and add (Fig.2.1):
such that $u\in V(s_{i})$ .
find: For $u\in U,$ $find(u)$ returns$link(s_{i})$ adds all the elements of $V(s,)$ to $V(s_{i+1})$ , and modifies thelink: Foris updated toordered partition to $P(U,S-\{s_{i}\})$ . By link.
$split(u)$$s_{i}:=find(u)$
$u\in
U-S,$
split: For
and then divides the set
first executes, the other allwithinto two sets, one containing allwith$P(U,S\cup\{u\})$$(u),$$\nu>u$ .
. By split
The ordered partition is modified tois$S\cup\{u\}$updated to.
$\nu\inV-U$, let
add: Forbe defined by $\nu^{*}=\min\{u|u\in U\cup\{n+1\}, u>\nu\}$ . For
andinserts into
. The ordered partisuch that$(v,v^{*}),$$P(U\cup\{\nu\},S)$tion becomes. By add
is updated to. (Notethat, in add
satisfying the above condition is given in advance with )Concerning the general problem in which find, link, split and add operations are
executed, we can execute each of them in $0(\log n)$ time by means of balanced trees.
However, special cases of the problem can be solved more efficiently in an amortized
sense as follows. The problem in which find and link operations are only executed is akind of the set-union problem In fact, it is a special case of the set-union problem,
because the link operation can unite adjacent two sets in ordered partition only. For

Let $V=\{1,\ldots,n\}$ , and

$S$

and

$U$

$S\subseteq U\subseteq V$$s_{p+1}$$s_{0}$$U$$u_{i}\in V(s_{i})$$S=\{s_{1},\ldots,s_{p}\}$$u_{j}\in V(s_{j})$$U$$u_{i}<u_{j}$

$S$

$U$

$s_{i}\in S$$s_{i}\in S,$$(s_{i}),$$S$$S-\{s_{i}\}$$V(s_{i})$$\nu\in V(s_{i})$$\nu\leq u$$\nu\in V(s_{i})$$S$$\nu^{*}\in U$$\nu^{*},$$add(\nu, \nu^{*})$

$\nu$

$\nu$

$V(s_{i})$$\nu^{*}\in V(s_{i})$$U$$(\nu, \nu^{*}),$$\nu^{*}$$U\cup\{\nu\}$$\nu.$-2-

$Z4^{\mathfrak{t}}9$oooo eo
after add $(5,6)$ ; split(5)[fi nd (4) ]after link(3)[fi nd]$(\rceil)=6$$=5$

Fig.2.1. Ordered parti tions($o^{i}$

implies$i\in U;\bullet i$

impliesi$\in S$)

this problem, Gabow and Tarjan [5] showed the following.

ofis given in sorted order. Let
Theorem 2.1. [5] Suppose that a subset$n’=|U|$ . Then, starting with an ordered partition $P(U, U)$ , an intermixed sequence offind and ljnk operations can be executed in $O(m+n’)$ time and $O(n’)$ space.
$U$

$V$

$\square$$m$

The problem in which find and split operations are executed is the set-splitting problem first considered by Hopcroft and Ullman [6]. They showed that, starting with anordered partition $P(V,\otimes)$ , an intermixed sequence of find and split operations canbe executed in $O((m+n)\log^{*}n)$ time and $O(n)$ space. Gabow and Tarjan [5] showedthat the sequence can be executed in $O(m+n)$ time and $O(n)$ space.
, an intermixed sequence of
We call the problem, in which, starting withfind and split operations and 1 add operations is executed, the incremental set-splitting. It seems that this problem has not yet been studied expliproblem Note that
citly although it is rather straightforward to extend an algorithm for the set-splitting
problem to that for the incremental problem.
We first show that Hopcroft and Ullman’s [61 set-splitting algorithm can beextended to the incremental set-splitting problem. Specifically, we show the following.
$m$$P(\emptyset,\emptyset)$$m$$l\leq n$, a sequence ofTheorem 2.2. Starting with an empty ordered partition$0((l+m)\log^{*}l)$add operations can be executed intimefind and split0(1)space.
and$P(\otimes,\otimes)$$m$$operations_{\urcorner}and\square l$

Define a function $F(i)(i\geq 0)$ by $F(O)=1$ and $F(i)=F(i-1)2^{F(i-1)}(i\geq 1)$ . Also,
define a function $G(l)(1\geq 1)$ by $G(l)= \min\{i|F(i)\geq l\}$ . Note that $G(l)$ is. Hopcroft and Ullman’s set-splitting algorithm [61 uses aand increases very
tree defined as follows. A node of level in the tree is a leaf, and does not have any
sons, hence it has at mostson. A node of level $i(\geq 1)$ has between one and$F(i)$ leaves. A node of levelis called complete if it has $F(i)$ leaves among its descendants, and is called incomplete, otherwise.
$\Theta(\log^{*}l)$$s\hat{l}owly$$0$$2^{F(i-1)}$

$i$

-3-

$z$

se

We keep the ordered partition by the following data structures. The ground set
is kept by a list in the increasing order from left to right. Each set in the ordered partition is made to correspond to a tree the root of which contains the name of the set.
A set of leaves of all trees correspond to some subset $W$ of , and not necessarily to
the whole ground set , where each element such that split $(u)$ has been executed isin the set $W$. For each $u\in U$ , we record $p(u) \equiv\min\{u’|u’\in W, u’\geq u\}$ .
In order to execute find$(u)$ , we find the root of a tree that contains a leaf
corresponding to $p(u)$ , and return the name associated with that root. Concerning, and letin the list representing, we insert
in the left ofadd$p(\nu):=p(\nu^{*})$ . Consider the operation split $(u)$ . If $u\in W$ , we divide the tree containing
along a path from a leaf to the root of that tree as in Hopcroft and Ullman’s static
set-splitting algorithm. If, we first find a leafthat lies in the left of leaf $p(u)$among all the leaves, and then partition the tree containing along the path fromto the root as above (if $p(u)$ is the leftmost leaf, we do not partition any tree). Then,
to the tree containing , we add, from the right side, elements from the next elementin this order one by one. At this stage, if the number ofof to in the list ofsons of a node of level comes to be greater than $2^{F(i-1)}$ by making a new node oflevel $i-1$ , we make a new node of level and let the new node of level $i-1$ be a sonof the new node of level .
Let us evaluate the time complexity of the above algorithm. Bach add operation
takes a constant time, and each find operation takes a time linear to the height of atree. In the above algorithm, each non-leaf node can have at most two incompletesons, so that the height of a tree is at most $G(1)+1$ . Hence, each find takes $O(G(l))$
time.
Now we consider the complexity for executing split. Concerning incomplete
nodes, the number of incomplete nodes moved in one split operation is at most theheight of a tree, i.e., at most $G(l)+1$ , hence the total number of times to move an
incomplete node is $O(lG(l))$ . The remaining problem is to count the number oftimes to move a complete node. For this purpose, we use the following techniqueoften used in analyzing the amortized time complexity of algorithms (see Tarjan [221).
In adding a new leaf, we put real-valued chips on non-leaf nodes, and, in moving acomplete node, we consume one chip of the father of the node. Then, the number oftimes to move a complete node is bounded by the number of chips put in the courseof the algorithm if the number of chips on each non-leaf node does not become negative at any stage of the algorithm.
A non-leaf node having complete sons is called admissible if either (i) it has atleast $k+(k\log k)/2$ chips and its rightmost son is complete, or (ii) it has at least$k+(k \log k)/2+\max\{0, (\log(k+1))/2+2-d\}$ chips where its rightmost son is incomplete and requires leaves in order to become complete. If a non-leaf node is admissible, the number of chips on it is nonnegative.
We now show the following, from which, with the above discussions, Theorem 2.2
is obtained.
$U$

$U$

$U$

$(\nu,\nu^{*})$

$u$

$U$

$\nu^{*}$

$\nu$

$u$

$u\not\in W$

$w$

$w$

$w$

$w$

$w$

$U$

$u$

$i$

$i$

$i$

$k$

$d$

Lemma 2.1. The total number of times to move a complete node in all the split
operations is $O(lG(1))$ .

-4-

251
Proof: We put chips as follows: In adding a new leaf to a tree, we put two chips
on each non-leaf node on the path from the leaf to the root. Then, the total numberof chips needed is $O(lG(1))$ , hence, we have only to show that all the non-leaf nodes
are admissible in the computation when we put chips as above.
The number of chips changes when a leaf is added to a tree, or a tree is partitioned into two. We flrst consider the case when a leaf is added to a tree. New nodes
created at this stage are apparently admissible. Among old nodes whose chips are
modified by this operation, a node, whose rightmost son is not changed and is still
incomplete, remains admissible, too. Among those old nodes, consider a node whoserightmost son becomes complete. This node currently has $[k+(k\log k)/2]+$$[2+(\log(k+1))/2]$ chips, whose number is easily seen to be greater than $(k+1)+$$((k+1)\log(k+1))/2$ . Hence, this node is admissible. Among old nodes, consider anode whose rightmost son is a node newly created at this stage. Let be the level ofthis node. In the case of $i=1$ , this node is easily seen to be admissible. In the case of$i>1$ , since $k\leq 2^{F(i-1)}-1$ , we have$i$,$k+ \frac{1}{2}k\log k+2+\frac{1}{2}\log(k+1)-(F(i-1)-1)\leq k+\frac{1}{2}k\log k+2$

and so this node is admissible.
Next, consider the case when a tree is divided into two. Consider a father node
whose complete sons are divided into two, where two cases occur. In the first case,a complete son among those sons is divided into two incomplete nodes to both left
. Suppose that the other $k-1$ complete nodes are distributed intoand right
nodes in the left and right trees, respectively. Note that $k_{1}+k_{2}+1=k$ . By simand
ple calculation, we have
$k$

$k$

$t^{J}rees$$k_{1}$$k_{2}$$\min\{k_{1},k_{2}\}+[(k_{1}+\frac{1}{2}k_{1}\log k_{1})+(2+\frac{1}{2}\log(k_{1}+1))-1]+(k_{2}+\frac{1}{2}k_{2}\log k_{2})$.

$\leq k+\frac{1}{2}k\log k$chips in moving complete nodes, chips left can be distriAfter consuming
buted so that two nodes corresponding to the original father node are admissible.
completeandIn the second case, $k=k_{1}+k_{2}$ complete sons are divided into
nodes in the left and right trees, respectively. Then we have$\min\{k_{1},k_{2}\}$$k_{1}$$\min\{k_{1},k_{2}\}+(k_{1}+\frac{1}{2}k_{1}\log k_{1})+(k_{2}+\frac{1}{2}k_{2}\log k_{2})\leq k+k\log k$$k_{2}$.

Hence, after consuming $\min\{k_{1},k_{2}\}$ chips, chips at hand can be distributed so that two
nodes corresponding to the original father node are admissible.
Next, extending Gabow and Tarjan’s algorithm, we show the following.
$\square$

Theorem 2.3. An intermixed sequence of find and split operations and add
operations can be executed in $O(l+m)$ time and 0(1) space with $O(n)$ preprocessing
and extra space of size $0(n)$ for the answer table.
Proof: Since almost all of Gabow and Tarjan’s algorithm for the set-splitting problem applies to the incremental problem, we note only those parts of their algorithm
which should be modified or remarked in the incremental problem.
$m$

-5-

$l$

.

$rr\dot{\epsilon}^{r}J^{O}$in order to obtain $O(l+m)$
The first problem is how to represent the ground set
bound. We use three levels of set: microsets, mezzosets and macrosets. (Since weemploy the parent encoding scheme as described below, two level of sets seems to beis partitioned into consecutive elements,
insufficient for our purpose.) The set$|\logn|$
in such a way that there is $O(|U|/\log n)$ mezcalled mezzosets, of size at mostzosets. Each mezzoset is partitioned into consecutive elements, called microsets, ofsize at most $|\log\log nJ$ in such a way that the number of microsets inis$0(|\tilde{U}|/\log\log n)$.
The second problem is how to execute the table-lookup method on microsets sothat add operations can also be executed efficiently. In the static problem, eachmicroset is represented as a path, and is encoded into a single computer word throughits parent table. In the incremental case, we represent each microset by a forest
whose preorder gives an ordering of elements in the set in decreasing order, andencode it through the parent table.
, weThis enables us to execute add operations quickly as follows. In add
by makingthe parent of so that
add to the forest of the microset containing
the preorder of the augmented forest satisfies the above condition, which is possible
owing to the definition offor . If there comes to be a microset of size greaterthan $|\log\log n|$ by add, we first compute the preorder of the forest representing it, andthen partition it into two halves according to the preorder, which can be done in$O(\log\log n)$ time. If there comes to be a mezzoset of size greater than $|\log n|$ , wesimply divide it into two halves.
Concerning the table lookup on microsets, we construct the answer table forparent tables and mark tables, which is the preprocessing. Here we must redefine theanswer table for the incremental problem. Suppose that $f$ is the forest, and is amark table of it, andis a node in the forest. In Gabow and Tarjan [51,answer $(f,a,j)$ is defined to be the nearest marked ancestor of node in the forest $f$ .
For our problem, we redefine answer $(f,a,j)$ to be the nearest marked predecessor ofnode with respect to the preorder of $f$ . Concerning the redefined answer table,
given a forest $f$ and a mark table , we can compute the values of answer $(f,a,j)$ for
all nodes in the forest in time linear to the number of nodes, which can be done bytraversing the forest in preorder. Thus, the preprocessing, to construct the answer
table, can be done in $O(n)$ time and space.
The last problem to be mentioned is on the “relabel-the-smaller-half‘ method forthe incremental set-splitting problem, since we use it for the unsplit microsets and also
the unsplit mezzosets. It is noted that a sequence of find and split operations andadd operations
be executed intime by this method, which can beshown easily.
$U$

$U$

$\tilde{U}$$\tilde{U}$$(\nu,\nu^{*})$$\nu^{*}$$\nu$$\nu^{*}$$\nu^{*}$

$\nu$

$\nu$

$a$

$j$

$j$

$j$

$a$

$j$

$\tilde{l}$$\tilde{m}$$0(\tilde{m}+\tilde{l}\log\tilde{l})$$can\square$

Theorem 2.4. Consider sequences offind and split operations and add operations maintaining ordered partitions $P(U_{i},S_{i})$ whose ground set
are subsets, initially empty sets, of . We assume that, given an element of, we can find the$micro_{i}(u)$$number_{i}(u)$microset,, containing, ofand the number,within its
space (concerning micro andmicroset in a constant time, totally using
number , see Gabow and Tarjan [5]). Then, we can execute these sequences$l_{i}$$m_{i}$$U_{i}$

$V$

$u$

$u$

$U_{i}$$u$$0( \sum_{i}l_{i})$$()$$- 6-$$()$

253
simultaneously in $0(n+ \sum_{i}(l_{i}+m_{i}))$ time and $0(n+ \sum_{i}l_{i})$ space.

Proof: In each sequence, we use the same answer table. That is, in the preprocessing step, we construct only one answer table, which takes $O(n)$ time and space.
$micro_{i}(u)$ and $number_{i}(u)$ can be found in a
Due to the assumption that, forspace by theconstant time, we can execute each sequence in $0(l_{i}+m_{i})$ time andalgorithm in Theorem 2.3. Then, the total time and space complexities are $O(n+$and $0(n+ \sum_{i}l_{i})$ , respectively.
$u\in U_{i},$$0(l_{i})$$\sum_{i}(l_{i}+m_{i}))$$\square$

3. Dynamic Layered Segment Tree
3.1. Layered segment tree

In this section, we recall the layered segment tree, developed by Vaishnavi andWood [231, for the static orthogonal segment intersection search. Concerning intersections of parallel segments, the problem is essentially the one-dimensional intervalintersection problem, for which efficient dynamic data structures such as priority
search tree [18] are known. So, in the following, we consider the case in which a setof vertical segments is given, and a query is a horizontal segment. The case in whicha query is a vertical segment is analogous.
be a set of vertical segments. For simplicity, we assume thatLet
abscissae of vertical segments are different from one another. (It is easy to modify
our algorithm so that it can treat vertical segments with the same abscissa; for example, when several vertical segments with the same abscissa must be handled simultaneously, we record them by a list and make them represent by the value of theabscissa.) We can then suppose thatitself denotes the abscissa of vertical segment
the interval of with respect to ordinate. We suppose that
. Denote byis an open-closed interval, i.e. $(a,b$ ], and that all the endpoints of segments inhave integer values from 1 to with respect to abscissa and from 1 to $N(\leq 2n)$with respect to ordinate.
We now recall the segment tree due to Bentley [11. For an integer interval $(a,b$ ],a segment tree $T(a,b)$ consists of a root associated with interval $I(w)=(a,b$ ], andin the case of $b-a>1$ , of a left subtree $T(a,|(a+b)/2|)$ and a right subtree$T(|(a+b)/2|,b)$ ; in the case of $b-a=1$ , the left and right subtrees are empty (Fig.3.1, a nodeof $T(1,N)$ is called an t-\’{n}ode of ifand Fig.3.2). For(i)is the root of $T(1,N)$ and $L(\nu)\neq I(w)$ , or(ii) the parent of
is a t-node of , and $\emptyset\neq L(\nu)\cap I(w)\subset I(w)$ .
A node is called an s-node of if(i)is the root of $T(1,N)$ and $L(\nu)=I(w)$ , or(ii) the parent of
is a t-node of , and $I(w)\subseteq L(\nu)$ .
For each node of $T(1,N)$ , let $S(w)$ be the set ofsuch that is an s-node of$U(w)$, andbe the set ofsuch thatis an s-or t-node of . Note that
$S(w)\subseteq U(w)$ . We keep the set $S(w)$ by a doubly linked list in increasing order.
In the layered segment tree, we manipulate two kinds of ordered partitions. For
of $T(1,N)$ , we record an ordered partition $P(U(w),S(w))$ . Also, foreach nodeiseach non-root node , we record an ordered partition $P(U(w_{\pi}), U(w))$ where$U(w)\subseteq
U(w_{\pi})$)(note(Fig.3.3). Initially, we construct thesethat
the parent of$V\subseteq\{\nu_{1},\ldots,\nu_{n}\}$$\nu_{j}$$L(\nu_{i})$$\nu_{i}\in V$$\nu_{i}$$L(\nu_{i})$

$V$

$n$

$w$

$\nu\in V$

$w$

$\nu$

$w$

$w$

$\nu$

$w$

$\nu$

$w$

$w$

$\nu$

$\nu\in V$$w$$\nu\in V$

$v$

$w$

$w$

$\nu$

$w$

$w$

$w_{\pi}$

$w$

$-7-$

254
$v_{3}$$v_{4}$$v_{5}$$21435$$——————-v_{1,I_{-\underline{\ovalbox{\tt\small REJECT}}-\ovalbox{\tt\small REJECT}_{--}^{-\underline{\ovalbox{\tt\small REJECT}}_{----}^{-}}}^{-}}v_{2_{-}-}----------I_{--}^{--}--$$w_{31}$$w_{32}$$w_{33}$$w_{34}$

Fig.3.1. The segment tree $T(1,5)$

Fi g.3.2. Vertical segments$P(U(w_{34}),S(w_{34}))$

Fig. 3.3. The layered segment tree for vertical segments in Fig.3.2

structures, which can be done in $0(n\log n)$ time and space.
Let be a horizontal segment, whose interval with respect to abscissa is$h$$[h_{/},h_{r}]$and whose ordinate is $h_{o}(1</l_{0}\leq N)$ . Then the query for can be executed as follows.
QUERY:(i)findsuch that $\nu=\min\{\nu’|_{\nu’\in}V\cup\{n+1\}, h_{/}\leq\nu’\}$ by binary search;
if $\nu=n+1$ , then stop; otherwise, let be the root of $T(1,N)$ ;(ii) $s_{i}:=find(\nu)$ with respect to the ordered partition $p(U(w),S(w))$ ;report all the vertical segments $s\in S(w)$ such thatby traversing the list
$S(w)$;
representing$h$$\nu\in V$$w$$s_{i}\leq s\leq h_{r}$-8-$f55$;
be a son of with$\nu:=find(v)$ with respect to the ordered partition $P(U(w), U(w_{\sigma}))$ ;return to (ii);In the algorithm QUERY, each find can be executed in a constant time, hence
Vaishnavi and Wood’s theorem [23] is obtained.
(iii) if$w$

is a leaf, then stop; otherwise, let$h_{0}\in I(w_{\sigma})$$w$$w_{\sigma}$

Theorem 3.1. [23] The static orthogonal segment intersection search problem canbe solved in $0(\log n+k)$ query time and $O(n\log n)$ space where is the number of$k$reported intersections.

$\square$3.2. The insertion problem
In this problem, the set of vertical segments is updated by insertions. Concerning
queries, the algorithm QUERY given abOve works if we maintain respective orderedpartitions correctly. We now give an algorithm INSERT which inserts a vertical segment into the set with handling those ordered partitions correctly.
INSERT:(i)such that $\nu^{*}=\min\{\nu’|_{\nu’\in}V\cup\{n+1\}, \nu\leq\nu’\}$ by binary search;find
let be the root of $T(1,N)$ ;(ii) with respect to the ordered partition $P(U(w),S(w))$ ,; if is an s-node of , then split ;add
andbe the sons of ;if is a leaf, then return; otherwise, letwith respect to the ordered partition $P(U(w), U(w_{\lambda}))$ ,
; add
; if
is an s-or t-node of , then split ;with respect to the ordered partition $P(U(w), U(w_{\rho}))$ ,$\nu_{\rho}:=find(\nu^{*});add(\nu,\nu^{*})$ ;ifis an s-or t-node of , then split ;(iii) if
is a t-node of , thenthen
if
and return to (ii);ifthenand return to (ii);$\nu$$\nu^{*}\in V$$w$$(\nu,\nu^{*})$$w$$(\nu)$

$\nu$

$w$

$w_{\lambda}$$(\nu,\nu^{*})$$\nu_{\lambda}:=find(\nu^{*})$$w$$w_{\rho}$$w_{\lambda}$$\nu$$(\nu)$$\nu$$(\nu)$$w_{\rho}$

$w$

$\nu$

$L(\nu)\cap I(w_{\lambda})\neq\emptyset$$\nu^{*}:=\nu_{\lambda};w:=w_{\lambda}$$L(\nu)\cap I(w_{\rho})\neq\otimes$$\nu^{*}:=\nu_{\rho};w:=w_{\rho}$

It is seen that, in the step (ii) of INSERT,for satisfies the condition required
for executing add. It is then easy to show that the algorithm INSBRT correctly maintains all the ordered partitions. We now consider the complexity of the above algorithm.
$\nu^{*}$$\nu$

Theorem 3.2. An intermixed sequence of $0(n)$ queries and insertions can be executed in $O(n\log n+K)$ time and $O(n\log n)$ space, where $K$ is the total number ofreported intersections.
Proof: The above algorithm obviously takes $O(n\log n)$ space, so that we consider
the time complexity. Suppose that, in the sequence, there are queries and inserqueries except those parts for findtions, where $q+r=O(n)$ . In the query step,
operations can be executed in $0(q\log n+K)$ time. In the insertion step, insertions
except those parts for find, split and add operations can be executed in $O(r\log n)$ time.
In all the steps, suppose that, for the ordered partition $P(U(w),S(w))$ of eachnode of $T(1,N)$ , the find and split operations are executed $m_{0}(w)$ times, an the add
operation is executed $l_{0}(w)$ times. Also, suppose that, for the ordered partition$P(U(w_{\pi}), U(w))$ of each non-root nodeof $T(1,N)$ , whereis the parent of ,
$r$

$q$

$q$

$r$

$w$

$w$

$-9-$

$w_{\pi}$

$w$

256
the find and split operations are executed $m_{1}(w)$ times, and the add operation is executed $l_{1}(w)$ times. We consider that, for the root $w,$ $m_{1}(w)=l_{1}(w)=0$ . Then, we
have $\sum_{w}(m_{0}(w)+m_{1}(w))=O((q+r)\log n)$ and $\sum_{w}(l_{0}(w)+l_{1}(w))=O(r\log n)$ ,where the summations are taken over all the nodes of $T(1,N)$ .
Let us consider the complexity to execute sequences of $m,(w)$ find and split operaof $T(1,N)$ ). Owing to the strucadd operations ( $i=0,1$ ; all nodes
tions and$v\inV$
in some sequence, we can devise a procedure toture of the segment tree, givenin the sequence in a constant time. We then see that,and number
find micro
from Theorem 2.4, these sequences can be executed in $0(n+ \sum_{w}\sum_{i}(m_{i}(w)+l_{i}(w)))$time.
Thus, the whole sequence can be executed with the time complexity$w$$l_{i}(w)$$w$$(\nu)$$(\nu)$$0((q \log n+K)+(r\log n)+n+\sum_{w}\sum_{i}(m_{i}(w)+l_{i}(w)))$ ,which is $0(n\log n+K)$ .

$\square$

We next introduce a new operation, called right. For a set of vertical segments,,
such that $\nu=\min\{\nu’|\nu’=n+1$ or
the operation right $(i,j)$ finds$j\in L(\nu’)]\}$ .
$(i,j)$
That is, rightfinds the first segment in that meets a line stretching$(i,j)$
from a point
in increasing abscissa. We can execute this right operation by analgorithm similar to that for the query. In this case, we do not need traversing the list
of $S(w)$ , so that the following theorem is obtained.
$V$$[\nu’\in V,$ $i\leq\nu’$$\nu\in V$$V$

Theorem 3.3. An intermixed sequence of $O(n)$ right operations and insertions canbe executed in $O(n\log n)$ time and $O(n\log n)$ space.
$\square$3.3. The deletion problem
Using the operations link and find, we can efficiently solve the deletion problem.
to be deleted, we do not remove all the elements
Given a vertical segment
corresponding to from the data structure, but modify them so that will no more
be reported in queries. Specifically, on each s-nodeout ofof , we remove$S(w)$ . This makes the ordered partition $P(U(w),S(w))$ update. To obtain the
updated ordered partition, we have only to execute link . Combining this procedure
with the algorithm QUERY, we can solve the deletion problem correctly. For completeness, we describe below a procedure for deleting a vertical segment .
DELETE:(i)let be the root of $T(1,N)$ ;(ii) if
is an s-node of , then linkwith respect to the ordered partition $P(U(w),S(w))$ ;(iii) if
is a t-node of , thenletandbe the sons of ;ifthenand return to (ii);ifthenand return to (ii);
$\nu$

$\nu$

$\nu$

$w$

$\nu$

$\nu$

$(\nu)$

$\nu$

$w$

$w$

$\nu$

$w$

$(\nu)$$\nu$$w_{\lambda}$$w$$w_{\rho}$$L(\nu)\cap I(w_{\lambda})\neq\otimes$$L(\nu)\cap I(w_{\rho})\neq\otimes$$w:=w_{\lambda}$$w:=w_{\rho}$

The following theorem on the complexity can be obtained in a way similar to
Theorem 3.2 (we use Theorem 2.1 in place of Theorem 2.4), so that we omit theproof.

-

10-

$|^{v}$

S7

Theorem 3.4. An intermixed sequence of $O(n)$ queries and deletions can be executed in $O(n\log n+K)$ time and $O(n\log n)$ space, where $K$ is the total number ofreported intersections.
$\square$

4. Applications(1) Finding the connected and biconnected components of an intersection graph of orthogonal segments [9].
An intersection graph of segment@ in the plane is obtained by representing each seg$n$

ment by a vertex and connecting two vertices by an edge iff their corresponding segments intersect. In [9], it is shown that, if a sequence of $O(n)$ deletions and right
operations can be executed in $T_{D}(n)$ time and $S_{D}(n)$ space, the connected and biconnected components of the intersection graph can be found in $0(T_{D}(n))$ time and$O(S_{D}(n))$ space. Hence, from Theorem 3.3, we see that the connected and biconnected components can be found in $0(n\log n)$ time and $0(n\log n)$ space. Note that,
only for finding the connected components, $0(n\log n)$ -time and $O(n)$ -space optimalalgorithms, that use the plane-sweep technique, are known [41, [81.

Fig.4.2. Manhattan wi ri ng

Fig.4.1. Rectilinear regi on and a shortest
andpath between two pointscmetrirespect
to
in
$T$

$S$

$L_{1}$(2) Finding a shortest path, in respect tometric, between two $gi\nu en$ points in a rectilinear region with edges [12] (see Fig.4.1).
$L_{1}$$n$

A rectilinear region is a polygonal region whose edges are orthogonal segments, andmay contain “holes. In [12], Kojima, Sato and Ohtsuki showed that the problem canbe solved in $0(n\log n+T_{D}(n))$ time and $0(S_{D}(n))$ space. Hence, it is seen from
Theorem 3.3 that the problem (2) can be solved in $O(n\log n)$ time and $O(n\log n)$
space.
(3) Discerning the existence of a Manllattan wiring of nets on a single layer (Fig.4.2).
For pairs of points, called nets, on a grid, a wiring connecting all the pairs of
points by wires along grid lines is called a Manhattan wiring if the wires do not intersect one another and no wire has more than one bend. This problem was first considered by Raghavan, Cohoon and Sahni [201, who gave $0(n^{3})$ -time algorithm.
Masuda, Kimura, Kashiwabara and Fujisawa [171 gave an $0(n^{2})$ -time algorithm byconsidering an intersection graph of possible wires and employing depth-first searchtechnique on that graph. Imai and Asano [91 gave an efficient implementation of theiralgorithm. Using the implementation with the data structure considered in this paper,
we obtain an $O(n\log n)$ -time algorithm for this problem (3).
$n$

$n$

-

11

-

258

Fi g.4.4. Minimum number of parti tion
into disjoint rectangles

Fig. 4.3. Maximum number of
non-intersecting segments

orthogonal segments such that no two of horizontal ones and no twoof $\nu ertical$ ones intersect, a maximum number of non-intersecting segments (Fig.4.3).
This problem is equivalent to finding a maximum independent set of an intersection graph of those segments, and, in this case, the intersection graph is bipartite, sothat a maximum independent set can be found quickly. Combining the techniquesdeveloped in [91 with the data structure for the deletion problem, we can show that
this problem can be solved in $O(n^{3/2}\log n)$ time and $O(n\log n)$ space.
(4) Finding, among$n$(5) Partitioning a $gi\nu en$ rectilinear region with$n$edges into a minimum number of disjoint

rectangles (Fig.4.4).
Algorithms for this problem w\‘ere given in [151 and [191. The main step of thosealgorithms is the problem (4), and so we can solve this problem in $O(n^{3/2}\log n)$ time

and $0(n\log n)$ space.
The above problems are applications of the algorithm for the deletion problem.
Here, it should be noted that, concerning the problems $(1\sim 5)$ , a simpler data structure which gives the same results as above is given in Imai and Asano [91 by using
proper structures of those problems. Also, note that a data structure similar to that in[91 is independently developed in Lipski [141.

We below present two applications of the algorithm for the insertion problem.
(6) Finding the closure of a set of rectangles with orthogonal sides [161.
A region,in the $(x,y)$ -plane is called closed if, for any pair of points,
with $(x_{1}-x_{2})(y_{1}-y_{2})<0$ which are connected in , we have
. The unique smallest closed region containing is called the closure of .
In [161, Lipski and Papadimitriou considered the problem of finding the closure of aset of given rectangles with orthogonal sides (Fig.4.5).
The algorithm given in [161 can be implemented so as to run in $O(n\log n)$ time
and $O(n\log n)$ space by using the algorithm for the insertion problem. Here, it
should be noted that, concerning the problem itself of finding the closure of rectangles, an $O(n\log n)$ -time and $0(n)$ -space optimal algorithm, which is different fromthat in [161 and uses the plane-sweep technique, is known [211.
$n$

$R$

$(x_{1},y_{1})$$(x_{2},y_{2})\in R$$R$$(x_{2},y_{1})\in R$

$R$

$n$

-

12

-

$(x_{1},y_{2})$

$R$

S5$

Fig.4.5. The cl osure of a set of rectangles(7) Partitioning a rectilinear region into disjoint rectangles by adding $O(n)$ chords one by

one in aorder.
This problem can be solved in $0(n\log n)$ time and $0(n\log n)$ space. This problem can be used in several other problems. Here, we take up the problem of partitioning a rectilinear region into disjoint rectangles in such a way that the sum of theperimeters of those rectangles is as small as possible. This problem is known to be
NP-complete [111, and several heuristics have been considered. For example, consider the following simple heuristic (see Fig.4.6).
$gi\nu en$

(a)

(b)

Fig.4.6. Minimum perimeter partition into disjoint rectangl es(a) Concave points
with di rected segments$P$$l_{P}$(b) Approxi mate sol uti on

For each concave point in the given rectilinear region, stretch horizontal andinto the region until they meet anvertical directed segments starting fromedge of the region; take the shorter of the two, and denote it by .
(ii) Arrange all the concave points
in the increasing order of the lengths of .
(iii) In that order, stretch and add a segment starting fromin the direction of

(i)

$P$

$P$

$l_{P}$$P$$l_{P}$$P$-13-$l_{P}$

t60
until it meets an edge of the region or another segment that has aiready been
added to the region.
In this heuristic algorithm, the main step is just the problem (7), and so this heuristic
can be executed in $O(n\log n)$ time and $O(n\log n)$ space.
Acknowledgment
The authors thank Professor Y. Kambayashi of Kyoto University for informing
them of the paper [211.

References[11 J. L. Bentley: Solutions to Klee’s Rectangle Problems, unpublished note, Department of Computer Science, Carnegie-Mellon University, 1977.
[21 B. Chazelle: Filtering Search: A New Approach to Query-Answering. Proceedingsof the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson,
1983, pp.122-132.
[31 H. Edelsbrunner: Dynamic Data Structures for Orthogonal Intersection Queries.
Report 59, Institut f\"ur Informationsverarbeitung, Technische Universitat Graz,

1980.
H. Edelsbrunner, J. van Leeuwen, T. Ottmann and D. Wood: Connected Components of 0rthogonal Geometric Objects. Report 72, Institut f\"ur Informationsverarbeitung, Technische Universitat Graz, 1981.
[5] H. N. Gabow and R. B. Tarjan: A Linear-Time Algorithm for a Special Case of
Disjoint Set Union, July 1982, submitted to Journal of Computer and System Sciences (also cf. Proceedings of the 15th Annual ACM Symposium on Theory ofComputing, Boston, 1983, pp.246-251).
[6] J. E. Hopcroft and J. D. Ullman: Set Merging Algorithms. SIAM Journal on
Computing, Vol.2 (1973), pp.294-303.
[7] H. Imai and T. Asano: An Efficient Algorithm for Finding a Maximum Matchingof an Intersection Graph of Horizontal and Vertical Line Segments. Papers of theTechnical Group on Circuits and Systems, CAS 83-143, Institute of Electronics andCommunication Engineers of Japan, 1983.
[81 H. Imai and T. Asano: Finding the Connected Components and a Maximum
Clique of an Intersection Graph of Rectangles in the Plane. Journal of Algorithms, Vol.4 (1983), pp.310-323.
[91 H. Imai and T. Asano: Efficient Algorithms for Geometric Graph Search Problems. Research Memorandum RMI $83- 05$, Department of Mathematical Engineering and Instrumentation Physics, University of Tokyo, 1983.
[101 H. Imai and T. Asano: Dynamic Orthogonal Segment Intersection Search.
Research Memorandum RMI $84- 02$, Department of Mathematical Engineering
and Instrumentation Physics, University of Tokyo, 1984.
[111 D. S. Johnson: The NP-Completeness Column: An Ongoing Guide. Journal of
A lgorithms, Vo1.3 (1982), pp. 182-195.
[121 I. Kojima, M. Sato and T. Ohtsuki: A Shortest Path Algorithm on a Planar Rectilinear Region (in Japanese). Papers of the $Tec/mical$ Group on Circuits and
[41

-14-

$d\mathcal{L}$

[13]
[14]
[15]

[161

[17]

Sl

Systems, CAS 83-205, Institute of Electronics and Communication Engineers ofJapan, 1984.
W. Lipski, Jr.: Finding a Manhattan Path and Related Problems. Networks,
Vo1.13 (1983), pp.399-409.
W. Lipski, Jr.: An $O(n\log n)$ Manhattan Path Algorithm. Research Report 141,
Laboratoire de Recherche en Informatique, Universite de Paris-Sud, 1983.
W. Lipski, Jr., E. Lodr, F. Luccio, C. Mugnai and L. Pagli: On Two Dimensional
Data 0rganization II. Fundamenta Informaticae, Vo1.2 (1979), pp.245-260.
W. Lipski, Jr., and C. H. Papadimitriou: A Fast Algorithm for Testing for Safety
and Detecting Deadlocks in Locked Transaction Systems. Journal of Algorithms,
Vo1.2 (1981), pp.211-226.
S. Masuda, S. Kimura, T. Kashiwabara and T. Fujisawa: On Manhattan Wiring
Problem (in Japanese). Papers of the Technical Group on Circuits and Systems,
CAS 83-20, Institute of Electronics and Communication Engineers of Japan,

1983.
[181 B. M. McCreight: Priority Search Trees. Technical Report CSL-81-5, Xerox Palo
[19]

[201

[211

[221

Alto Research Centers, 1982.
T. Ohtsuki, M. Sato, M. Tachibana and S. Torii: Minimum Partitioning of Rectilinear Regions (in Japanese). Transactions of Information Processing Society ofJapan, Vol.24, No.5 (1983), pp.647-653.
R. Raghavan, J. Cohoon and S. Sahni: Manhattan and Rectilinear Wiring. Technical Report 81-5, Computer Science Department, University of Minnesota, 1981.
B. $Soisalon- So|ninen$ and D. Wood: An Optimal Algorithm for Testing for Safety
and Detecting Deadlocks in Locked Transaction Systems. Proceedings of the 1st$ACM$ Conference on Principle of Database System, 1982, pp. 108-116.
R. E. Tarjan: Data Structures and Network Algorithms. Society for Industrial and-15-