Graphics Reference
In-Depth Information
CHAPTER 17
Computational Geometry Topics
17.1
Introduction
This chapter considers a few selected problems from the field of computational geom-
etry. Section 17.2 discusses range trees and Section 17.3, interval and segment trees.
These data structures are then used in Section 17.4 to answer questions about when
bounding boxes intersect. Section 17.5 describes a simple approach to convex hull
intersections. The polygon triangulation problem is considered in Section 17.6.
Finally, Voronoi diagrams and the associated Delaunay triangulations are discussed
in Sections 17.7 and 17.8, respectively.
17.2
Range Queries
This section describes data structures that are useful in answering range queries.
Although the problem of responding to such queries in an efficient manner is inter-
esting in its own right, the main reason for including it here is that some of the mate-
rial is needed in the next section, which is on efficient bounding box intersections. In
general, though, it is worth pointing out that range queries arise not only in geom-
etry, where one might want to know which of a collection of points lie in a certain
range, but also in other areas. For example, in the context of an employee database
one might one to find out which employees are between 20 and 30 years old, make a
salary of between $40,000 and $60,000, and have between one and three children.
Since it will be convenient to interpret the term “box” in a generic n-dimensional
sense and to restrict ourselves to boxes whose sides are parallel to coordinate axes,
we begin with a definition.
An
axis-parallel
n-dimensional box in
R
n
is any set of the form
Definition.
[
]
¥
[
]
¥¥
[
]
ab
,
a b
,
...
a
nn
,
,
11
2 2
where a
i
£ b
i
.
