Algorithms in a Nutshell

(^256) | Chapter 9: Computational Geometry

• Given an input set of line segments, can there be horizontal or vertical segments?


• Given a set of points, is it possible that three points are collinear (that is, can
  be found on the same mathematical line in the plane)? If not, the points are
  said to be in general position, which simplifies many algorithms.


• Does the input set contain a uniform distribution of points? Or is it skewed or
  clustered in a way that could force an algorithm into its worst-case behavior?
  Most of the algorithms presented in this chapter have unusual boundary cases
  that are challenging to compute properly; we describe these situations in the code
  examples.

Classic Problems in Computational Geometry

We motivate the algorithms described in this chapter by presenting several of the

classic problems that, in a sense, define the field of computational geometry. To

solve these problems efficiently, one must know several key data structures and

algorithmic techniques that will prove useful in other domains as well. We

describe each problem and briefly describe and analyze an initial intuitive algo-

rithm to determine the expected running time to solve the problem. In the

remaining sections of this chapter, we present more elegant and efficient algo-

rithms for solving these problems. As we have repeatedly said in this book, the

obvious solution can usually be improved by: (a) taking advantage of the unique

aspects of the problem, and (b) storing information using an appropriate data

structure that supports the algorithm.

Convex hull

Given a set of pointsPin a two-dimensional plane, the convex hull is the smallest

convex shape that fully encloses all points inP; a line segment drawn between any

two points within the hull lies totally within it. The hull is formed by a clockwise

ordering ofhpointsL 0 ...Lh–1. The first pointL 0 is typically the leftmost point*in

the setP(although any point can be the start). Each sequence of three hull points

Li,Li+1,Li+2creates a right turn; note that this property holds forLh–2,Lh–1,L 0 as

well.

Givenn points, there are C(n,3), or:

different possible triangles. Pointpi∈Pcannot be part of the convex hull if it is

contained within a triangle formed by three other distinct points inP(for

example, in Figure 9-4 pointp 6 can be eliminated by the triangle formed by points

p 4 ,p 7 , andp 8 ). For each of these trianglesti, a brute-force algorithm could elimi-

nate from the convex hull any of then–3 remaining points if they exist withinti.

Once the hull points are known, a clockwise ordering is determined by selecting

the leftmost point as the “base” (in this casep 0 ) and sorting all remaining points

* If multiple points exist inPwith the samexcoordinate, thenL 0 is the one with the smallesty

coordinate.

n

⎝⎠ 3

⎛⎞ nn()–^1 ()n–^2

6

=---------------------------------------

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use