■

1. INTRODUCTION

To simplify the presentation, we assume that all the endpoints of all the rectangles are disjoint.

表現を簡潔にするために、全ての長方形の頂点は他の長方形と接していない (disjoint) ものとする。

For a node x in a tree T, we denote by n(x) the number of descendants of x in T.

tree T の node x について、n(x) と記した時は T の node x の子孫の数とする。

We also denote by p(x) the parent of x in T.

p(x) と記した時は、 T の node x の親とする。

When we use these notations the tree we refer to will be clear from the context.

これらの表記を使えば、言及した木は文脈から明らかとなる。

For a rectangle r we denote by rx and ry its projections to the x and y dimensions, respectively.

長方形 r について rx と ry と記した時は、各々 x, y 次元への写像である。

2. INTERVAL TREES

Interval trees store a set of intervals such that we can efficiently report all intervals intersecting a query point. 区間木は区間の集合を保持する。質問点と交差するすべての区間を効率的に見つけるために。

Let S be the set of intervals, let |S| = n, and let X be the set of endpoints of the intervals in S. S を区間の集合とする。|S|=n , X をSに属する区間の終端点の集合とする。

An interval tree for S consists of a primary balanced binary tree Tp where the leaves store the endpoints X, from left to right in symmetric order. 区間木 S は平衡二分木 Tp からなる。Tp において葉は終端点Xを保存し、左から右に左右対称である。

We use the dynamic version of interval tree, where the points of X can be arbitrary points on a line. 我々は動的な区間木を用いる。動的区間木では、終端点 X は線上の任意の点とりうる。

(The static version of an interval tree is for the case where X is a static set known in advance). 静的な区間木は X は事前に静的な集合としてしられている。

For each internal node v ∈ Tp we define the followings.

個々の中間 node v ∈ Tp について、以下のものを定義する。

The split point of v, denoted by split(v), is the search key of node v.

v の分割ポイント split(v) は node v の検索キーです。

I.e. split(v) is a number such that the leaves of the left subtree of v store points smaller than split(v), and the leaves of the right subtree of v store points larger than split(v).

即ち split(v) は数である。どのような数かといえば v の左副木の葉が保持している点（の値）は、split(v) よりも小さくなる。また v の右副木の葉が保持している点（の値）は、 split(v) より大きくなる。（ここで言う points とは endpoints X のことか）

The range of v, denoted by range(v), is defined recursively as follows.

v の領域 range(v) は再帰的に次のように定義される。

The range of the root is (−∞,∞].

root の領域は (−∞,∞]

For a node v, where range(v) = (l, r], the range of the left child of v is (l, split(v)], and the range of the right child of v is (split(v), r].

range(v) = (l, r] となる node v においては、v の左の子の領域 r_l は (l, split(v)]、v の右の子の領域 r_r は (split(v), r] である。（なるほどだから root の部分も左開右閉区間なのか）

5. 5. EXTENSIONS TO HIGHER DIMENSIONS

The segment tree Ty partitions the plane into strips parallel to the x-axis each corresponding to a different node of Ty.

セグメント木 Ty は平面を細切れに分割する。細切れ(strips, segment のこと?)は x 軸と平行であり、個々の細切れは異なる Ty のノードと対応している。

The rectangles stored at one node v of Ty cover the y-strip corresponding to v and the search among them is a one dimensional problem.

あるひとつのTy のノード v に保持されている長方形は v に対応した y-strip を保持している、そしてそれらの間での検索は１次元の問題である。