6 - Computing with Configurations

Summary

Howmany triangles are there in the configuration of Figure 6.1? To answer this, one needs either some mathematical insight or tedious calculation. But performing tedious calculations is something computers do well. So, how could a computer be used to solve this puzzle?

Input Representation

Before we ask how to design a program to find triangles or other subconfigurations in larger configurations, we need to consider how a configuration can be described as the input to a program. In the case of Figure 6.1, the configuration is already shown with grid lines, making it easy to represent its points using integer Cartesian coordinates. But not every configuration can be represented in this way (see Chapter 13 for details). Even the configurations that do have integer coordinate representations sometimes need huge numbers for those coordinates, forcing algorithms with this kind of input to use multiprecision arithmetic and complicating their analysis.

Instead, for algorithms on configurations, we will generally assume only that our algorithms have some way to identify the points of a configuration and to determine the orientations of triples of points. Algorithms that access their input in this limited way are more versatile. They can handle inputs using explicit coordinates for the points, as long aswe can compute orientations from coordinates. But they can also handle a three-dimensional matrix of orientations as input. It would even be possible for such an algorithm to take as its input a number of points and a pointer to a subroutine that maps triples of indexes to the orientation of the points with those indexes. When analyzing these algorithms,we will assume that each orientation test takes constant time, but if not, the time bounds we state should be multiplied by the time per orientation test.

Despite being restricted in this way, it is still possible for an algorithm to carry out many important geometric tasks, such as the construction of the convex hull of the input points. Recall from Chapter 1 that the convex hull is a convex polygon, the smallest convex polygon that contains the set. Figure 6.2 shows an example. For points that are not all on a single line, the convex hull may be determined from the order type, as follows.