?
ööhm, bei dem abschnitt über die datenstruktur kapier ich irgendwie gar nichts mehr:
To simplify the notation, we scale the coordinates so that r = 1. Let S = {d1 , . . . , dn }
be a set of unit disks, q ∈ R2 , and let the operation member(q, S) return a disk di ∈ S
containing q, and ∅ if no such disk exists. In order to implement our algorithm, we need a
data structure that supports efficiently membership queries and deletion of disks.
To that end, we divide the plane using the axis-parallel grid Γ consisting of orthogonal
cells of edge length 1/2 that passes through the origin. Since the disks have unit radius,
each disk intersects O(1) cells, hence, only O(n) cells have a non-empty intersection with
disks of S. We maintain these cells in a balanced search tree (ordered lexicographically).
For each such cell Q, we maintain a list of disks whose center lies in Q, and a data structure
Q
Db , which maintains the upper envelope of Sb —the disks set of disks that intersect Q, and
whose centers lie below the line containing the lower boundary of Q. (The upper envelope
Q
of Sb consists of all points p ∈ Q ∩ D∈S Q D such that no point of this union lies above p.)
b
Similar data structures Dl , Dr and Da are maintained for SlQ , Sr and Sa , the set of disks
Q Q
intersecting Q whose centers lie (respectively) to the left of, to the right of and above the
lines containing the left, right and upper boundaries of Q. The space needed for Db will be
Q
shown to be O(|Sb |), and similarity for the other data structures. Since each disk intersects
O(1) grid cells, the space requirement for all these data structures is O(n).
To answer the query member(q, S), we consider the cell Q of Γ containing q in its interior
(we ignore the degenerate and easy situation that q is on a boundary of a cell). If the center
of a disk di lies inside Q then q ∈ di , and can be output as di = member(q, S). Otherwise,
Q
we use Db to find if any disk of Sb contains q, which happens if and only if q lies below the
Q
upper envelope of Sb . We repeat this process (if needed) for Dl , Dr and Da .
Let us describe Db . The data structures Dl , Dr and Da are similar. Similar data structure
was also used by Sharir [44]. Db is similar to the segment tree (Overmars and van Leeuwen
Q
[42]) and the one used by Hershberger and Suri [30]. Order the disks of Sb from left to
right by their centers, and construct a complete binary tree T whose leaves are these disks.
With each node v ∈ T we associate the set S(v) of disks corresponding to the leaves of the
subtree rooted at v. Let UE(v) denote the upper envelope of S(v). As easily seen, not all
the disks of S(v) must participate in UE(v), but those that do, appear along UE(v) (when
scanned, from left to right) in the same order as the order of their centers, from left to right.
Und zwar ist mir unklar, wie ich mir das mit dem 'envelope' vorstellen muss.