ind on
TS that
ICtures
DCEL)
ex and
in and
angles.
elation
DCEL
on that
jangles
undary
ointers
ie CDT
'onquer
1980).
are not
its. We
] delete
yith the
gn) on
e is the
ed: one
srations
S (~ 10
1 of the
is very
follows
es raise
ons and
ould be
e going
We are
; region
Antonio Ruiz
32 Point location and bucketting
The optimal point location cost is O(log(n)) in time. If we want to insert n points, for each of them we have to perform a
point location and so the cost of triangulation in the real RAM model is O(n log(n)), and this is optimal.
Point location by Lawson navigation or by ray following is O(n) (Lawson, 1977), but with data points homogeneously
distributed as they are found in practice the average cost is O(n2) (Guibas and Stolfi, 1985). One of the reasons for
incremental triangulation beeing suboptimal is because point location is suboptimal. The updating is also suboptimal
because the number of edges to be swaped due to a point insertion depends on the data distribution and it can be the whole
set. On average with the data sets found in practice the number of triangles that need to be updated after the insertion of a
point is low. We need to improve point location and one solution to do this is to build a tree and to perform a search on it.
If the tree is balanced, point location can be performed in O(log(n)) time.
We have chosen a bucket point-region quadtree (bucket PR-quadtree or BPRQT) to store the vertices of the triangulation.
The triangulation is a data oriented partition of the plane while the region quadtree is a regular partition of the plane in
which the data only determines the depth of the tree. The quadtree (QT) has the twofold mission of improving point
location and of keeping partially sorted the information stored into disk.
The idea of storing a triangulation in a QT is not new. Chen et al. (Chen, 1990) also used a quadtree to store a triangulation
but they stored at most one triangle per leaf.
A BPRQT is a quadtree (QT) in which a leaf subdivides into four by halving in each direction (Samet, 1990b). A leaf can
contain points up to a maximum or threshold. If we want to insert one more point then the leaf subdivides into four and
the contained points are redistributed between the new sibling leaves. Figure 2 shows the triangulation of Davis sample
data set (Davis, 1973) in a BPRQT for a threshold of 4 points per leaf. Practical thesholds are larger. We apply a threshold
of 400 points/leave.
7 [22 23 T 32-1 rS
6 i r 7 | T, -
(/ -
5 20 212 | 1213” gp ai
k | ; | J
| | | 210 | 241
4r | +
oz x] 3 / 12 TIS
3l | ; À
2 + | | Jd
002 K-T003 7072 013 10 rw 113
1 - | ! I 1 A N —
000 001 0170 011| / T0 71
0 1 t "n ui 1 1
0 1 2 3 4 5 6 7
Figure 2: Triangulation of a sample set of points in a bucket PR-quadtree
We have extended the BPRQT in the following way: each leaf contains also a pointer to one interior edge or to an edge
close to the center of the leaf. We name this edge the "central edge". Point location is performed in two steps. First
We search in the QT the containing leaf. Then the search proceeds as a Lawson navigation following the DCEL pointers
starting on the central edge of the leaf.
The algorithms for the management of a BPRQT of points are described in Samet ((Samet, 1990a), (Samet, 1990b)). A
maximum depth must be defined because when points are very close there is no warranty to separate them by halving
Space a few times. Another problem with the PR-quadtree is the low average occupation of the leaves. The leaves are
void at the beginning, when a leaf fills it subdivides and the contained vertices are redistributed between 4 siblings. We
did a numerical experiment with real data to find the average occupation of leaves. After a few oscillations the average
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 787
