C++ For Mathematicians (2006) [eng]

206	C++ for Mathematicians

133 b /= r;

134

135double xx = x1 * a + x2 * b;

136double yy = y1 * a + y2 * b;

137double zz = z1 * a + z2 * b;

138

139return PObject(xx,yy,zz);

140}

141

142

143 PObject PObject::op(const PObject& that) const {

144

145 if (equals(that)) return PObject(0,0,0);

146

147double c1 = y*that.z - z*that.y;

148double c2 = z*that.x - x*that.z;

149double c3 = x*that.y - y*that.x;

150

151return PObject(c1,c2,c3);

152}

When the test program (Program 10.10) is run with the new PObject class, we achieve the desired results.

The random point P is (-0.479902,-0.616199,1)
Two lines through P are L = [0.384191,1.32364,1]
and M = [1.66531,0.32589,1]
Is P	on L? 1
Does	M have P? 1
The point of intersection of L and M is Q = (-0.479902,-0.616199,1)
Is Q	on L? 1
Does	M have Q? 1
P and Q are equal

The user may invoke PObject::set_tolerance(0.0); to revert to the previous behavior (exact checking).

Finally, the method we use for testing near equality can be improved. For example, we check if two projective objects are equal by computing their L1 distance and comparing against tolerance. Alternatively, to check x1,y1,z1 and x2,y2,z2 for equality, we might consider a test such as this:

	|x1 − x2| + |y1 − y2| + |z1 − z2|	≤ ε	.
	|x1| + |x2| + |y1| + |y2| + |z1| + |z2|

Whatever equality test you feel is most appropriate, it is only necessary to edit one method (equals in PObject) to implement your choice.

The Projective Plane

207

10.9 Pappus revisited

We close this section with a program to illustrate Pappus’s Theorems and the use of the near-equality testing.

Program 10.13: A program to illustrate Pappus’s theorem and its dual.

1#include "Projective.h"

2#include "uniform.h"

3

4/**

5* An illustration of Pappus’s theorem and its dual

6*/

7

8void pappus() {

9seed();

10

11// two random lines

12PLine L1,L2;

13L1.randomize();

14L2.randomize();

15cout << "The two lines are " << endl << L1 << " and " << L2 << endl;

16

17// get three points on the first

18PPoint P1 = L1.rand_point();

19PPoint P2 = L1.rand_point();

20PPoint P3 = L1.rand_point();

21

22cout << "Three points on the first line are " << endl

23<< P1 << endl << P2 << endl << P3 << endl;

24

25// get three points on the second

26PPoint Q1 = L2.rand_point();

27PPoint Q2 = L2.rand_point();

28PPoint Q3 = L2.rand_point();

29

30cout << "Three points on the second line are " << endl

31<< Q1 << endl << Q2 << endl << Q3 << endl;

32

33// find the three pairwise intersections

34PPoint X1 = (P2+Q3)*(P3+Q2);

35PPoint X2 = (P1+Q3)*(P3+Q1);

36PPoint X3 = (P1+Q2)*(P2+Q1);

37

38cout << "The three points constructed are " << endl;

39cout << X1 << endl << X2 << endl << X3 << endl;

40

41if (collinear(X1,X2,X3)) {

42cout << "They are collinear, as guaranteed by Pappus’s theorem"

43<< endl;

44}

45else {

46cout << "TROUBLE! The three points are not collinear!!"

208	C++ for Mathematicians

47<< endl;

48}

49}

50

51void dual_pappus() {

52// Two random points

53PPoint A,B;

54A.randomize();

55B.randomize();

56cout << "The two points are " << endl << A << " and " << B << endl;

57

58// Three lines through the first

59PLine L1 = A.rand_line();

60PLine L2 = A.rand_line();

61PLine L3 = A.rand_line();

62

63cout << "The three lines through the first point are " << endl

64<< L1 << endl << L2 << endl << L3 << endl;

65

66// Three lines through the second

67PLine M1 = B.rand_line();

68PLine M2 = B.rand_line();

69PLine M3 = B.rand_line();

70

71cout << "The three lines through the second point are " << endl

72<< M1 << endl << M2 << endl << M3 << endl;

73

74// Get the three dual Pappus lines

75PLine X1 = L2*M3 + L3*M2;

76PLine X2 = L1*M3 + L3*M1;

77PLine X3 = L1*M2 + L2*M1;

78

79cout << "The three lines constructed are " << endl;

80cout << X1 << endl << X2 << endl << X3 << endl;

81

82if (concurrent(X1,X2,X3)) {

83cout << "They are concurrent, as guaranteed by Pappus’s theorem"

84<< endl;

85}

86else {

87cout << "TROUBLE! The three lines are not concurrent!!"

88<< endl;

89}

90}

91

92

93int main() {

94double t;

95cout << "Enter desired tolerance --> ";

96cin >> t;

97PObject::set_tolerance(t);

98cout << "You set the tolerance to " << PObject::get_tolerance()

99<< endl << endl;

100

101pappus();

102cout << endl;

	The Projective Plane	209
103	dual_pappus();
104
105	return 0;

106 }

	Here are three runs of the program with the tolerance set to different values.
	Enter desired tolerance --> 0
	You set the tolerance to 0
	The two lines are
	[2.23943,2.19462,1] and [-0.685646,2.15228,1]
	Three points on the first line are
(14.3273,-15.0755,1)
(-0.434872,-0.0119093,1)
(-0.56911,0.12507,1)
	Three points on the second line are
(-2.29319,-1.19516,1)
(0.43878,-0.324843,1)
(7.8271,2.02884,1)
	The three points constructed are
(-0.323743,0.01554,1)
(6.49488,5.53439,1)
(-0.0728833,0.218581,1)
	TROUBLE! The three points are not collinear!!
	The two points are
	(0.576837,0.361625,1) and (-0.407185,0.0903103,1)
	The three lines through the first point are
[-1.45089,-0.450946,1]
[0.398283,-3.4006,1]
[18.9351,-32.9691,1]
	The three lines through the second point are
[2.2305,-1.01622,1]
[2.46456,0.0391258,1]
[2.51677,0.274485,1]
	The three lines constructed are
[2.42584,0.116742,1]
[1.63958,0.114103,1]
[3.10284,0.119014,1]
	TROUBLE! The three lines are not concurrent!!
	Enter desired tolerance --> 1e-16
	You set the tolerance to 1e-16
	The two lines are
	[0.55364,0.547428,1] and [1.05044,-0.347064,1]
	Three points on the first line are
(-0.0325509,-1.79381,1)
(-0.440495,-1.38123,1)
(1.76843,-3.61523,1)
	Three points on the second line are
(-2.34784,-4.22478,1)
(-0.911666,0.122021,1)
(-0.367147,1.77009,1)
	The three points constructed are

210 C++ for Mathematicians

(-0.421418,-0.561603,1)
(0.160804,-3.85329,1)
(-0.310677,-1.18769,1)
They are collinear, as guaranteed by Pappus’s theorem
The two points are
(-15.284,42.4406,1) and (-2.5346,1.29455,1)
The three lines through the first point are
[-1.32801,-0.501814,1]
[-0.903241,-0.348843,1]
[0.00499314,-0.0217642,1]
The three lines through the second point are
[2.56928,4.25793,1]
[0.38109,-0.0263314,1]
[31.5203,60.9412,1]
The three lines constructed are
[-0.725517,-0.0128931,1]
[-9.98448,-16.6938,1]
[-0.936431,-0.392874,1]
TROUBLE! The three lines are not concurrent!!
Enter desired tolerance --> 1e-12
You set the tolerance to 1e-12
The two lines are
[0.52502,-0.458764,1] and [-0.330266,1.96863,1]
Three points on the first line are
(-2.99912,-1.25249,1)
(-1.44265,0.528772,1)
(-2.39671,-0.563076,1)
Three points on the second line are
(1.18674,-0.308875,1)
(1.38413,-0.27576,1)
(-6.11116,-1.53321,1)
The three points constructed are
(-4.23015,-0.702403,1)
(30.568,1.77536,1)
(1.20682,-0.315271,1)
They are collinear, as guaranteed by Pappus’s theorem
The two points are
(15.562,5.35536,1) and (-0.432665,0.837712,1)
The three lines through the first point are
[-0.171104,0.310479,1]
[-2.21649,6.25412,1]
[-0.915338,2.47313,1]
The three lines through the second point are
[-3.3276,-2.91238,1]
[0.807493,-0.776671,1]
[-9.38979,-6.0434,1]
The three lines constructed are
[-2.58492,5.62249,1]
[-2.64901,-1.39739,1]
[-2.6087,3.01846,1]
They are concurrent, as guaranteed by Pappus’s theorem

The Projective Plane

211

10.10 Exercises

10.1Create a pair of classes named Rectangle and Square, which should be a derived subclass of Rectangle.

Rectangle should have two data members (representing the height and width) and the following methods.

•A two-argument constructor.

•Methods to get the height and width.

•Methods to change the height and width.

•Methods to report the area and perimeter.

Square should have a single-argument constructor (which should rely on Rectangle’s constructor). It should have the same methods as Rectangle, except that the methods to change height and width should modify both the height and width.

10.2Create a class called Parallelogram that represents a parallelogram seated in the plane as shown in the figure.

(b,c)

(a,0)

The values a and c must be nonnegative; b may be any real value.

The Parallelogram should define a zeroand three-argument constructor and methods for computing the area and perimeter of the figure.

Next, create two subclasses named Rectangle and Rhombus from the parent class Parallelogram. Define appropriate two-argument constructors for these subclasses.

There is no need to make a new area() method for the subclasses; the parent’s area() method is efficient and serves the subclasses well. However, the perimeter() method in the Parallelogram needs to invoke the sqrt procedure to find the side length from (0,0) to (b,c). However, the subclasses can find the perimeter in a more efficient manner. So, although it isn’t necessary to redefine perimeter() for Rhombus and Rectangle, do so anyway so these procedures are more efficient in the special cases.

212	C++ for Mathematicians

10.3In Exercise 8.3 we explored C++’s inability to hold complex<double> values in a set container because the complex<double> type does not define a <

operator. We resolved that issue by making a set of pair<double,double> objects that held the values (x,y) in lieu of x + yi.

Create an alternative solution by creating a class named mycomplex that is derived from the complex<double> type. Add to mycomplex an operator<. You also need zero-, one-, and two-argument constructors (with double arguments); these should invoke complex<double>’s constructors.

Finally, write a short main() procedure to check that mycomplex objects can be housed in a set<mycomplex> container.

10.4Define a pair of classes named Point and Segment to represent points and line segments in the plane. The Point class should include an operator+ method; the result of P+Q is the line segment joining the points. The Segment class should include a midpoint() method that returns the Point that is midway between the end points of the line segment.

For both classes, define operator<< for writing to the screen.

10.5In C++ it is possible to have two classes, Alpha and Beta, such that arguments and return values for methods in one class may be the type of the other class. That is, an Alpha method might return a Beta value and vice versa. (This is the case for the Point and Segment classes in Exercise 10.4.)

Can we create classes Alpha and Beta so that each contains data members that are of the other type?

10.6Extend the complex<double> class to include the value ∞ (complex infinity) by creating a derived class named Complexx. This new value should interact with finite complex values in a sensible way. For example,

∞ + z	= ∞	for finite z
∞ × ∞	= ∞	for z = 0
z ÷ 0	= ∞
z ÷ ∞	= 0	for finite z

Some calculations with Complexx values should yield a special undefined value; for example, 0 ÷ 0, ∞ ± ∞, 0 × ∞, ∞/∞, and so on.

Your class should include the operators +, - (unary and binary), *, /, ==, !=, and << (for writing to the screen).

10.7Use the PPoint and PLine classes to write a program to illustrate Desargues’ Theorem: suppose that triangles ABC and DEF are in perspective from a point O. (That is, the triples OAD, OBE, and OCF are each collinear.) Then the three points of intersection of the lines AC and DF, lines AB and DE, and lines BC and EF are collinear (see the points X, Y , and Z in Figure 10.4).

The Projective Plane

213

O

C

A

B Z Y

E

F

X D

Figure 10.4: An illustration of Desargues’ Theorem.

Chapter 11

Permutations

Let n be a positive integer. A permutation is a one-to-one and onto function (i.e., a bijection) from the set {1,2,...,n} to itself. The set of all permutations of this set is denoted Sn.

One way to represent a permutation π is as a list of values [π(1),π(2),...,π(n)]. For example, π = [1,4,7,2,5,3,6] means π S7 and π(1) = 1, π(2) = 4, π(3) = 7, and so on, and π(7) = 6.

The disjoint cycle notation is an alternative way to write permutations. The permutation π = [1,4,7,2,5,3,6] is written (1)(2,4)(3,7,6,5). The (1) means π(1) = 1. The (2,4) means π(2) = 4 and π(4) = 2. The (3,7,6,5) means π(3) = 7, π(7) = 6, π(6) = 5, and π(5) = 3. In other words, (1)(2,4)(3,7,6,5) means this:

1 7→1

2 7→4 7→2

3 7→ 7→6 7→5 7→3.

In this chapter we develop a C++ class to represent permutations. We have two goals. One is to introduce additional C++ concepts (copy constructors, destructors, and assignment operators). The other is to write a program to explore Ulam’s problem.

11.1Ulam’s problem

Given a permutation π Sn, we may regard π as a sequence [π(1),π(2),...,π(n)]. An increasing subsequence of π is a sequence [π(i1),π(i2),...,π(it )] where 1 ≤ i1 < i2 < ··· < it ≤ n and π(i1) < π(i2) < ··· < π(it ). A decreasing subsequence is defined analogously. A subsequence of a permutation is called monotone if it is either increasing or decreasing.

For example, the sequence [1,4,7,2,5,3,6] contains the increasing subsequence [1,2,3,6] and the decreasing subsequence [7,5,3]. Every permutation must have a “reasonably” long monotone subsequence. This is a consequence of the Erdos˝– Szekeres Theorem.

Theorem 11.1 (Erdos˝–Szekeres). Let k be a positive integer and let n = k2 +1. Then every permutation π Sn contains a monotone subsequence of length k + 1.

Informally, the result states that every permutation in Sn contains a monotone sub-

√

sequence of length about n. The proof of this result is interesting both because it

215