Mastering Algorithms with C

Questions and Answers

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 ₁ , p ₂, and p ₃, we determine the orientation of p ₃ relative to p ₂ with respect to p ₁ by treating the line segments from p ₁ to p ₂ and p ₁ to p ₃ 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, ...