**Q:** One application of
geometric algorithms mentioned at the start of this chapter was
determining whether the track of an object transgresses a restricted
region. If we assume that the track we follow begins outside of the
restricted region, a simple approach to this problem is to determine
whether any line segment in the track intersects with any line segment
defining the restricted region. What is the running time of this
approach if we use the *lint* operation presented
in this chapter?

**A:** The runtime complexity of
this approach is *O *(*nm*),
where *n* is the number of line segments in the
track and *m* is the number of line segments
defining the restricted region. This is because for each of the
*n* line segments in the track, we call
*lint* once for each of the *m*
line segments in the restricted region. Since
*lint* runs in a constant amount of time, the
runtime complexity of the solution overall is *O*
(*nm*).

**Q:** Determining the orientation of two points with respect to a third is an
important part of the algorithms presented for determining whether
line segments intersect and computing convex hulls. Formally, given
points *p* _{1 },
*p* _{2}, and
*p* _{3}, we determine the
orientation of *p* _{3}
relative to *p* _{2} with
respect to *p* _{1} by treating
the line segments from *p* _{1}
to *p* _{2} and
*p* _{1} to
*p* _{3} as vectors U and V. We then use the sign of the z-component of the cross product U × V as a gauge of orientation. What is the orientation of the points if we compute the cross product V × U? In other words, ...

Start Free Trial

No credit card required