Algorithms in a Nutshell

(^252) | Chapter 9: Computational Geometry
Two-dimensional structures (lines, rectangles, and circles) have three-dimensional
counterparts (planes, cubes, and spheres) and evenn-dimensional counterparts
(such as hyperplanes, hypercubes, and hyperspheres). For advanced computa-
tional geometry problems, the type of input data can expand to higher
dimensions.
We first describe a set of core interfaces for the computational geometry domain
and then introduce a set of classes that realize these interfaces. All algorithms are
coded against these interfaces to enable maximum portability.
The algorithms in this chapter depend upon a set of core concepts, shown in
Figure 9-1:
IPoint
Represents the basic Cartesian point (x,y) using double floating-point accu-
racy. Provides a default comparator that sorts byx, from left to right, and
breaks ties by sortingy, from bottom to top.
IRectangle
Represents a rectangle in Cartesian space; can determine whether it inter-
sects anIPoint or contains anIRectangle.
ILineSegment
Represents a finite segment in Cartesian space with a fixed start and end
point. In “normal position,” the start point will have a higherycoordinate
than the end point, except for horizontal lines (in which case the leftmost end
point is designated as the start point). It can determine intersections with
otherILineSegmentorIPointobjects; it can determine whether anIPoint
object is on its left or right when considering the direction of the line from its
end point to its start point.
Do We Need More Than Three Dimensions?
Computational geometry problem: Given a set of 14 million points in a 29-
dimensional plane, find the closest neighbor for each point.
Real-world service:The eHarmony matchmaking service (http://www.eharmony.
com) claims it is “the first relationship service on the Web to use a scientific
approach to match highly compatible singles.” Using their patented (U.S. Patent
No. 6,735,568) Compatibility Matching System™, eHarmony predicts the long-
term compatibility between two people. All users of the system (estimated to be
14 million by February 2007) fill out a 436-question Relationship Question-
naire. eHarmony then determines closeness of match between two people based
on 29 dimensions. eHarmony reported in November 2003 that 91% of its users
received 10 or more potential matches.
Dataimputationproblem:An input file contains 14 million records, where each
record has 29 fields with text or numeric values. Some of these values are
suspected to be wrong or missing. We can infer/impute “corrections” for the
suspicious values by finding other records “close to” the suspicious records.
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